前言

为什么会有这个东西呢？主要是我在做这个题单的时候，发现省选的时候这些算法都过过一遍，但是掌握情况相当的差。其他的题单也有部分的知识是我没有掌握到的。

所以，为了更好的完成这些题单，也为了为之后在省选有完备的的资料可查，或者为之后的人铺平道路，整理以下的内容。

。

为了能够及时更新，你会在我拖更的地方看到这样一句友情提示：

这里有你没写完的东西，杂鱼...

大纲

动态规划

常见基础动态规划

 

 

 

 

背包

 

 

 

 

动规常见优化

倍增优化

数据结构优化

动态DP

图论

最短路

floyd

spfa

dijkstra

johnson

差分约束

最小生成树

prim

kruskal

最近公共祖先(LCA)

tarjan(连通分量问题)

scc(强连通分量)

割边-edcc(边双连通分量)

割点-vdcc(点双连通分量)

点分治

二分图

网络流

FF-EK-Dinic

费用流

上下界流

模拟费用流

2-SAT

二分图最大权匹配

最小树形图

仙人掌与圆方树

数据结构

树状数组

线段树

序列线段树

动态开点线段树

值域线段树

可持久化线段树

线段树合并

线段树分裂

ZKW线段树

并查集

普通并查集

扩展域并查集

权值并查集

莫队

普通莫队

带修莫队

回滚莫队

树上莫队

笛卡尔树

树套树

线段树二分/树状数组倍增

多树二分

整体二分

CDQ分治

线段树分治

重链剖分

长链剖分

平衡树

Splay

FHQ-Treap

(李超线段树)

(动态树)

(快速傅里叶变换)

(快速数论变换)

Prufer序列

可并堆

斜堆

随机堆

左偏树

KDT

ODT(珂朵丽树/颜色段均摊)

数学

质数的判定

暴力

埃氏筛

欧拉筛

Miller–Rabin

更相减损法

欧几里得法(gcd)

裴蜀定理

扩展欧几里得法(exgcd)

欧拉定理

拓展欧拉定理

中国剩余定理(CRT)

扩展中国剩余定理(EXCRT)

卢卡斯定理(Lucas)

扩展卢卡斯定理(exLucas)

卡特兰数

威尔逊定理

错排列

圆排列

多重集排列组合

BSGS与EXBSGS

生成函数

普通生成函数

指数生成函数

狄利克雷生成函数

狄利克雷卷积

莫比乌斯反演

亚线性筛法

杜教筛

PN筛

min_25筛

第一类斯特林数

第二类斯特林数

斯特林反演

二项式反演

Burnside定理

Polya定理

博弈论

二次剩余

线性基

行列式

字符串

字符串哈希

KMP

KMPAM(KMP自动机)

失配树

马拉车(Manacher)

EXKMP

ACAM(AC自动机)

SAM(后缀自动机)

SA(后缀数组)

计算几何

计几基础概念

 

tricks

搜索序限制区间

序列操作转差分

逐步可行

上升下降幂预处理组合数

哈希判等价类

尺取法

注：

：AM 在字符串中，默认指 ，即自动机。

动态规划

常见基础动态规划

背包

动规常见优化

动规的优化也是一门高深的学问。

动规核心要素包括状态、阶段和决策。动规的优化主要从第 方面入手进行优化。

对于状态，我们有时会通过题目中的性质，压缩掉其中的某些维度，比如 Mobile Service 一题中我们通过一定有一个员工在请求的位置，压缩掉了一维，省掉了一个 ；有时候我们会重新设计状态，使得他能够包括更多的本质相同的状态，比如固定点数的不同构 DAG 计数，等等。

更加常见的优化从对于决策，或者说转移的方面入手。一般来说我们会通过各种各样的手段，达到压缩转移次数（比如倍增优化，矩阵快速幂优化，CDQ优化等），快速找到决策点（比如单调队列优化，各种数据结构优化，斜率优化，贪心优化，四边形不等式优化等），快速统计转移贡献（比如前缀和优化，各种数据结构优化，离散化，贪心优化，费用提前计算等），以及各种各样针对问题特点特例化出来的各类模型（比如背包，树形DP，数位DP等）。

总而言之，我们的核心思想就是压缩状态，减少阶段，加速决策，从而达到更优的效率。

倍增优化

倍增优化的基础原理就是他把 段给暴力拆分成了 段，通过适当的预处理，将平均的时间复杂度中的 降到 。讲完了，看例题：

T1：有一些线段，问你至少要多少条线段才能覆盖掉 这个区间。

这个是最简单的一道题，可以预处理出每个左端点用 条线段最远能覆盖到哪个右端点， 解决。不给代码了。

T2。

我们不难发现暴力匹配的问题就在于太过暴力了（废话），所以我们考虑优化。

我们想到的第一个优化类似于建立索引，让你匹配的时候能够快速地跳到下一个该匹配的位置，但是实际上并没有优化复杂度。

第二个优化就比较关键了：我们考虑将字符串视为一个整体进行匹配，也就是说我们计算出跳完一整个 或者 需要在另一个字符串上跳多少。比如说这里我们选择让 表示已经匹配到了 的第 位，再走完一个 所能新匹配的字符数。

实际上，字符串长度是 级别的，我们可以直接暴力匹配预处理。

但是这样显然还不够，我们还能更进一步：反正你都处理出跳一次 的匹配的字符数了，不如再处理一下跳 次 的匹配的字符数。于是你成功的把时间复杂度降到了 。

参考代码如下：

T3。

其实本身难度并不是很大，首先处理出对于每一个节点两个人分别会怎么走，然后倍增处理出每一个节点两个人分别先走的情况下走 步两个人的开车距离增量以及新的位置。倍增就完了。

注意边界，可能换人。代码如下：

数据结构优化

动态动态规划

图论

最短路

floyd

floyd 是一种可以求全源最短路的算法，其时间复杂度为 。其思路比较接近动态规划。

具体地说，我们顺序枚举一个中转点 ，然后去更新每一对的 的最短路为 。这样子更新完之后， 实际上变成了经过 的点时的 之间的最短路。

一定要注意不要把 放到 里面枚举，因为这样子不满足 是经过 的点时的 之间的最短路。不过有研究表明把这样的循环执行三次也会有正确性？

代码如下：

spfa

spfa 的思路是逐步松弛，缩小点的最短路长度。

具体的来说，我们先将每个点的最短路长度设置为极大值，然后将起始点的最短路长度设为 ，将其放入队列中。

然后我们不停的取出队首，遍历其所有能到的点，如果有的点的最短路长度比从队首过来的更长，那就更新那个点的最短路大小。如果那个点不在队列中那就加入队列。

这个算法可以判断负环。显然如果一个点被更新了超过 次，那就一定有负环。时间复杂度是 的，随机数据下 ，但是实际上可以轻松卡到其上界限 。代码如下：

dijkstra

如果一幅图没有负权边，那么我们从小的向大的扩展一定不会错。因此，我们可以使用优先队列来维护最短路最短的没有扩展的点，并类似于 spfa 一样松弛其他的点。只不过因为没有负边权，所以第一次访问到就是最优解。代码如下：

johnson

johnson 是另一种可以处理负边权的全源最短路算法。他的思路是 通过将每一个点“抬高一点”，将边权转化为正权，然后处理。

我们引入一个物理上常见的概念，叫做“势能”。我们新建一个超级源点向每一个点连一条边，权值为 ，随后用 spfa 跑出到每一个点的最短距离 ，视为每一个点的“势能”。随后我们将 的边权重新标注为 。由最短路的三角形不等式可得这个边权是恒正的。

最后在求 的最短路时，。其中 是 diskstra 跑出来的虚拟距离。

为什么这样是正确的呢？我们注意到，在求 的最短路的过程中，势能的变化量永远是 ，和物理意义上的势能很像：势能绝对大小和选定的参考点有关，但相对大小与之无关，两点之间的势能差只与两端点有关，和中间怎么走的无关。

因此我们通过保证在任意两点之间的每一条路径的增加量相同的方式，保证了我们跑出来的最短路转化后仍然是最短路。

差分约束

差分约束可以用来求解形如 的不等式方程组。

具体的来说我们可以先通过调换顺序将不等号的方向同一，比如全部统一成 ，随后我们思考在最长路中的三角形不等式，发现 。形式一样。

于是 可以转化为 到 有一条长度为 边，然后随便找一个源点作起始点跑一下最长路就行了。

显然如果出现了正环，那么就无解，否则每个点的 就是一组合法的解。

最小生成树

prim

prim 的思路是加点。每一次我们选出和当前已选择的点集最近的点，并将它加入已选择的点集当中。

具体地说，最开始的时候，我们随意指定一个节点作为已选择的点集中的初始元素，并计算出每一个节点和他的距离。随后我们扩展 轮。每一轮我们找出距离最近的，加上他的距离，并将它纳入已选择的点集中。随后再用这个点去重新计算别的点的最短距离。这样扩展完之后 个点就都在已选择的点集中了。

时间复杂度 ，动用人类智慧的话就不清楚能做到多少了。

kruskal

kruskal 的思路是加边。每一次我们选出边权最小的边，并检查两个端点，如果两个端点不在同一个集合中，就把二者合并，并在贡献中加上这条边。否则不做处理。显然这个贪心策略不会出任何问题。

最近公共祖先

最常用的有 种解法：倍增，tarjan，dfs 序。

倍增法就是预处理出每一个结点的 级祖先。先将两个节点的深度调整一样，然后不停往上倍减着跳，最终二者相同的位置就是答案。参考代码如下：

tarjan 是一种可以做到严格线性的离线算法。通常情况下复杂度为 。

算法流程是这样的：我们先将询问同时记录在那两个点上，然后我们从根节点开始遍历。

每一次到一个节点 时，我们先去遍历他的所有子节点 并将 节点的并查集合并到 上。然后将 标记为遍历过。

最后检查 节点的所有查询 。如果 已经遍历过了那么答案就是 所在的并查集，否则不做任何操作。参考代码如下：

接下来是 dfs 序。dfs 满足一些神奇的性质，比如说 中深度最小的节点的深度恰为 的深度 ，如果 的 序比 小。

其实这个我不是很想证明，因为分讨一下 是不是 就证明完毕了。这样子你就可以用 ST 表做到 查询了。

tarjan

tarjan 的思路并不复杂，我们先按照 序进行遍历，然后处理每一个边。具体的来说，我们给每个节点两个标记：。 记录他的 序中的编号， 则是在一定的规则下通过至多一条不在搜索树上的边能到达的 dfs 序的最小值。

强连通分量

强连通分量是针对于有向图说的。具体的，如果同时存在 的路径，那么 强连通，而一个强连通分量 就是一个满足 ， 强连通的极大子图。

那么我们在 tarjan 的时候具体怎么办呢？到每一个点 时，我们会将 和 均设置为一个新的比之前都大的值。首先，如果一个点 发现了一个没有遍历过的点 ，那么我们就可以先继续遍历 ，随后将 取为 。这一种显然没有问题。

如果发现了一个遍历过的点那就要分一下情况了：

如果这个点已经被标记在某一个强连通分量中了，那说明这个点无法到达自己，肯定和自己不是同一个强连通分量内的。

但是如果没有被标记过呢？那么有两种情况：一种是访问到自己的祖先了，一种是访问到了自己的子节点。总之我们发现我们的这个边不是树边，而且因为那个节点截至目前仍然没有被纳入强连通分量，所以一定能到达自己，可以更新。

说白了，在强连通分量下，这个规则就是双方互相可达。但是似乎上面的最后一句的“一定能到达自己”不是很说的走呢？

并不是的。当我们在遍历完了 的所有子节点之后发现 ，那么不难想到这个点及其子树中的所有点其实都无法逃出 的魔爪，否则就会更新到 中。因此没被更新就是可以访问到自己。

还差最后一个问题：我怎么知道该标记哪些点是自己这个连通分量内的？当 的时候，我们会去标记在 的子树之下而且可达到 的节点。这些节点可以通过一个栈很轻松的维护出来。参考代码如下：

割边-边双连通分量

所有双连通分量都是针对无向图说的。割边定义为删除之后能够使整个图中的连通块数量增加的边。边双连通分量（简称边双）是不含有割边的极大连通子图。

具体怎么求呢？不难想到，按照 dfs 序，如果限制了不能走原边进行返祖的情况下仍然做到了返祖，那么意味着除了下来的那条边还有另一条通路向上回溯，也就是必定形成环。而且显然一个环上的边不会是割边。

总的流程至此已经比较容易想到了：我们首先初始化 和 ，然后找所有的非原边进行扩展。

如果扩展的是一个没访问过的点，就先搜索下去，最后将 值合并上来。特别的，如果只要求求出割边，那么可以在这一步判断子节点的 值和自己的 值。如果 值更大则是一条割边。

反之如果是一个访问过的点，就将 值合并上来。特别的，在这一步如果将 值合并上来实际上仍然是正确的，想想为什么。

最后，如果需要求出边双连通分量，就判断一下自己的 和父节点的 ，如果自己的更大就标记为一个新的边双，可以用和强连通分量类似的方式标记出来。

当然了，远古代码总是神奇的。我们可以将割边标记出来，最后 出边双。代码如下：

割点-点双连通分量

割点定义为删除之后能够使整个图中的连通块数量增加的点。点双连通分量（简称边点）是不含有割点的极大连通子图。显然一个点可以出现在很多个点双当中。

具体怎么求呢？不难想到，按照 dfs 序，如果限制了不能走原点进行返祖的情况下仍然做到了返祖，那么意味着除了下来的那条点还有另一条通路向上回溯，也就是必定形成环。而且显然一个环上的点不会是割点。

总的流程至此已经比较容易想到了：我们首先初始化 和 ，然后找所有的非原边进行扩展。

如果扩展的是一个没访问过的点，就先搜索下去，最后将 值合并上来。特别的，如果只要求求出割点，那么可以在这一步判断子节点的 值和自己的 值。如果子节点的 值不小于自己的 值则子节点是一个割点。一般来说，为了实现方便，如果需要求点双的话也会选择在这一步利用栈顺带维护了。

如果是访问过的节点，那么只要不是父节点，就可以选择向上跳到其 ，因此将其 值合并下来。

另外，上述方法显然并没有考虑到根节点的特殊性。不过不难想到，当且仅当这个节点是一个孤立的节点时，才会成为一个特殊的不被统计的点双；当且仅当这个节点下有至少两个独立的子树的时候他才是一个割点。

割点的判断代码如下：

点双的求解代码如下：

点分治

好久没有遇到了，感觉都快忘掉了，然而是一个很有启发性的算法。我就直接上强度了。请看例题。

这道题已经是点分治的一个比较综合的应用了，不过我们通过这道题来逐步拆解点分治的惯用思路。

首先，我们思考暴力怎么做的：我们枚举一个起点，去找满足要求的中点。还有很多暴力，这只是最容易想到的一种。不过不难注意到本质上都是在枚举树上的路径。

那如果我能够加速树上的路径的枚举，是不是就可以优化时间复杂度呢？这便是点分治的出发点。

有了出发点，我们还需要一个合适的切入点。也就是说我们需要找一些特征值，使得对于任意一条路径都有，而且不能够太多，还要尽可能容易枚举。说了这么多，我们也不难想枚举到路径的途径点，比如 。具体来说，我们处理当前子树时，我们枚举一个点作为必经点，处理当前子树内的经过途径点的路径的贡献，然后递归下去处理删去当前点后剩下的更小的子树。

我们注意到，枚举途径点之后，你势必要枚举当前处理的子树内的所有节点。但是 并不是那么的好用，尤其是遇到了链的时候，直接退化到 ，用不了！

不过我们注意到，如果我们把划分的过程按层拼接，就会发现每一层都会把几乎原先的一整颗树遍历完。因此，限制层数就是必要的。我们回想起重心是满足所有子树的大小均不超过原树大小的一半的神奇节点。因此我们每一次指定必经点为当前子树的中心，就能够限制层数为 的了！

所以说，点分治一般的流程就是找到当前子树的重心，处理经过重心的路径的贡献，删去重心并以相同方式递归处理子树。假设对一颗大小为 的树计算贡献的时间复杂度是 的，那么时间复杂度可以运用主定理，将整个过程看作二分进行计算。对于较为快速 ，例如 或 等，可以将整体的时间复杂度视作 。

还没有完，光有一层壳是没什么用的，我们还需要去尝试一下怎么设计经过点的路径的贡献计算。

这道题当中，我们注意到拼接路径的 为 。直接计算这个东西似乎是不容易的，因此我们考虑二分答案，将求极值转化为存在性检验。不难想到，如果我们在一开始就给每条边减去 ，那么限制就是 ，其中 为当前检验的答案。

其实这个东西不好限制的，当时就直接卡在这里了，因为分子分母只确定了一个。不过注意到 恒正，所以我们考虑对于 和 的情况分开验证。推出相应的式子之后使用尺取法即可做。

也就是说内层合并信息的时候可能会用到的不只是数组，线段树等等的神奇数据结构，也可能是其他的各类神奇的技巧一拥而上。总之遇到这类问题的时候，建议多思考一会儿。

二分图

二分图是这一个图 ，可以分出两个点集 ，满足 且 或者 。

判定

有多种办法可以判定，常用的有染色法，扩展域并查集等。

染色法就是尝试给每个节点分配集合。显然如果 ，那么 ，换个集合仍然成立。

所以就随便钦定一个点在某个集合里，能分出来就有，分不出来就没有。

扩展域并查集类似，如果二者有就将 和 分别绑定一下。

最大匹配

就是给你一张二分图，问你能从里面选出多少边，满足这些边的左右部点都不重。

这个常用网络流中的 Dinic 或者匈牙利算法解决。

匈牙利算法就是不停的强制让某个点匹配上，如果某个右部点已经匹配上了就把他抢过来，直到成功匹配到没人的或者确实配不上。

网络流的话每一个左部点从源点牵一个流量一的，右部点连一个流量一的到汇点，中间的流量一就行。

霍尔定理

令 分别表示左右点集，那么定义 。也就是说 是左部点 所直连的右部点的集合。

再定义 。也就是说 是左部点子集 中存在点直连的右部点集合。

再约定 表示集合 的大小。

那么， 存在 向 的完全匹配。

显然和匈牙利算法的证明等价。必要性显然，充分性反证：

设G中不存在完全匹配，取 的一个最大匹配 ，则 中至少有一个点不在 上，且该点必至少与一条不在 中的边相连。

该边的另一个顶点若也为 非饱和点，则与 为最大匹配矛盾，若另一个顶点为 饱和点，则考察在 中与该顶点相邻的点，利用饱和点去考察在 中相邻的饱和点（交错地考察，即交错地通过 中的边和非M中的边），直至考察完毕。

由相异性条件知，最后必考察至非饱和点，此时出现一条增广路，又与假设矛盾（不是最大匹配），故充分性成立。refer。

扩展定理：

  1. 中最大匹配的情况下最多有 个点失配。
  2. 中每个点在匹配 个右部点的情况下仍然存在满最大匹配。
  3. 如果左部点 最多能匹配 个右部点，那么 存在满最大匹配。

证明的话，第一个可以让每个左部点同时连上 个赛博右部点，转化为原定理，得证。

第二个和第三个可以让第 个人裂成 份去分别和几个右部点连边，转化为原定理，得证。

但是解题是有技巧的，限制数是 级别的，我们需要去抓最紧的限制。也就是将有效限制个数缩到最小。从而求解问题。

网络流

FF-EK-Dinic

FF(Ford–Fulkerson) 增广思路

FF，即 Ford–Fulkerson 增广。该方法运用贪心的思想，通过寻找增广路来更新并求解最大流。

其中有一个概念叫做增广路，说白了就是所有边剩余流量大于零的路径。使用这条边显然可以使答案增加，但是直接贪心是错的。

接下来，我们进行反悔贪心。当我们给 这条边增加 的流量时，就将 的剩余流量减去 ，而将 的剩余流量增加 。

正如 OI-wiki 的一张图：

可以严格证明，这里略去。反正不考证明。其本质上就是 最大流-最小割 定理。

EK 算法

使用 BFS时，FF 增广表现为 EK 算法。其本质上就是将找出任意一条变成了找出最短的一条，每次使用 BFS 找出最短的增广路并增广。时间复杂度为 。时间复杂度劣，而且和 Dinic 难度大致相当，不附代码。

Dinic 算法

他的优化就在于他同时对多条增广路进行处理，具体的流程如下：

首先，对当前的图做一次 BFS，求出每个点的“深度”。

然后，进行 DFS。每次 DFS 时，记录当前节点和当前携带流量。随后，一直向深度大 的子节点分配尽可能多的流量，直到没有子节点或者自己流量用完。贡献就是所有被分配到的子节点的贡献之和。

这里还常用一个“当前弧”优化，其实说白了，就是之前已经被分配满的子节点以后不可能再分配了，因此记录一个已枚举位置就行。参考代码如下：

费用流

对于没有负圈的普通费用流，常用 SSP(Successive Shortest Path) 进行求解，思路类似于 FF，每一次找一条或多条单位费用最大/小的路进行增广。

负圈是指单位费用为负的圈。

注意费用流的时间复杂度是 的， 是最大流。可以被卡到 。

给出基于 Dinic 的参考代码如下：

上下界流

正如其名，原先只有上界的网络流也有下界拉！一篇较好的博客专讲基础上下界流。

存在性判定

对于每一个点，我们令 ，然后思考：

  1. 对于 的点，其入度的下界与出度的下界相同，也就是说这些边我们可以将上界重写为 ，仍满足流量守恒。
  2. 对于 的点，他若直接将上界重写为 ，则不满足流量守恒，出度过小。需要向超级汇点连一条容量上界为 的边。
  3. 对于 的点，他若直接将上界重写为 ，则不满足流量守恒，入度过小。需要从超级源点连一条容量上界为 的边。

此时，若从超级源点到超级汇点满流，则存在，反之不存在，由源汇点的流量与原图的流量守恒关系不难证得。

有源状态下的判定

从 向 连一条容量无限的边，就完美地将有源强转成了无源，然后就能做了。

最大/小流(有源)

我们还是先有源强转无源跑判定，判定完了之后记录 到 的最大流，删除 到 的边，然后分情况：

如果是最大流，就跑出 到 的最大流和开始的那个最大流相加得到结果。

如果是最小流，就跑出 到 的最大流和开始的那个最大流相减得到结果。

问什么正确呢？其实判定的本质就是强制流量守恒，也就是强制将上下界流改成普通流。

判定如果成功的话，那么所有的点都在同一个“势能面”上了，多余的就是在推流/反流。

比如针对两个的缝合题红石科技，我们可以这样写：

最大/小费用可行流

基于我们前面所讲的判定的本质就是强制流量守恒，我们不管在建出来的辅助图上跑网络流还是费用流，反正只要限定是最大流，就能对应出原图的一个可行流。

所以说，我们建出辅助图并且提前计算砍去下界少算的费用，辅助图的最大/小费用最大流就是原图的最大/小费用可行流。比最大/小流(有源)还少一步。

核心代码如下：

当然还是别忘了要给原图中的 建一条没费用的无限流。

模拟费用流

思路类似于手动消元，说白了就是利用建出来的图的性质进行针对性的优化，从而加速计算。例题1。

在这道题中，建模其实非常的裸，但是点数过大，完全不能跑费用流，因此需要手动最短路。

那怎么做呢？我们注意到原图近似是一个二分图，也就是说任意一条路径可以视为 ，任意多条 和 拼接而成的。第三段费用为 ，所以只用分别维护第一二段从每个 出发的最优边。

给出一份仅保留核心的参考代码：

例题2，同样非常好建模，但是不难发现边太多了，没法玩。

所以我们可以从最大流-最小割定理入手，算他的最小割。显然，因为图只有一层，即每一个城市对应的点都直连源汇，所以每一个点要么断源，要么断汇。

显然断汇的点仍有能力向后面的城市流货，而断源的不能，所以写一个 DP 出来就完了。核心代码如下：

2-SAT

记得我们曾经学过一个东西叫做“扩展域并查集”，说白了就是令每一坨 的区间中的点 对应表示 在 状态下与别的状态的联系。两个点在一起就认为两个点对应的状态必定同时满足。

那这玩意这么好用，能不能用到 2-SAT 上呢？

很可惜，需要改一下题才能用得到。把或改成异或就行了。

思考一下并查集的底层逻辑：两个点对应的状态必定同时满足。换言之，你只能加双向边。

然而 2-SAT 并不是这样的，他用的是或，也就是说硬性的约束条件是： 和 。都是单向的约束。

那我们思考一下这些限制中的强连通分量意味着什么？

显然，这意味着这些点对应的状态成立与否是相同的。同时我们就推出了如果 与 在同一个强连通分量内，那么必定无解。

强连通分量怎么求呢？Kosaraju 和 tarjan 你选一个吧。

当然了，2-SAT 只是一个最直接的应用。其实他给我们提供的是一种单向限制的处理思路，适用性比 2-SAT 本身要更广很多。

顺带讲两个常用优化技巧：

线段树优化建图

T1rt，弱化版。

翻译一下就是有 个数 和 个数 ， 次从 或 中选出一个数放入 ，排序后询问最小的 。

我们可以假定 。解法大概率会是二分答案。首先如果 ，那么这俩不能同时出现。以此来建边进行求解，复杂度 。可以过弱化版。

但是这样并不够优，究其原因是我们需要大量的向一个区间内的点建边。

而这，我们显然可以使用线段树优化建边来飞过去。具体方式可以看下面这幅图：

比如本来是 要向 和 两个区间建边。

现在我们可以对原本的 区间建一颗线段树如图：

那这时候 向 连等同于向 连，向 连等同于向 连。

显然这样下来每次要连的边数锐减至 条。总复杂度降至 。

比较核心的就是这坨：

前缀优化建图

T2rt。

题意简单明了，转化也非常的明显，但是问题也就出在了这里。

相当于说在同一个部分内的 ，一定要 到 连一条边。只要我把所有的点放在同一个部分内，你的边数就是 的。包炸的。

所以现在就是要去优化这个东西。我们不难发现，其实如果我们将这个部分内的点任意排序，那第 个点一定要向第 都连上边。

线段树优化建图不太好使，因为数据范围真的够大。但是思考如下结构：

不难注意到，如果我们给整个部分添加两个辅助的侧链基团，那么这时候指向 就间接指向了 ，指向 就间接指向了 。

非常妙，此题可解。我们称这种建图方式为前缀优化建图。比较核心的代码就是这坨：

二分图最大权匹配

从最基础的二分图最大权完美匹配讲起走：

最常用的是 KM 算法。他的思路是这样的：

首先我们假定原图存在完美匹配。然后，我们给每个点分配顶标 ，满足 。

我们再取出 ，满足 ，那么这时候，当 中存在完美匹配时， 就是答案。

正确性： 限定了每一条边都会具有的单调性，从而限定了整体的单调性（感性理解）。

算法流程：

首先令 。显然满足限制条件。

接下来尝试扩大 。在匈牙利算法中，从一个节点寻找然后匹配失败所遍历的树被称为交错树。显然，其中匹配上的边与没匹配上的边交错出现。

我们如果能在交错树上找到一条的路径，并将这条路径上的左部点 ，右部点 ，那么不会让交错树上原有的边消失，而且可能会出现新的匹配，从而增大 。

为了防止一次性减小过多， 应取为 ，其中 在交错树上， 不在交错树上。

不难发现这样操作，交错树原有边不变，而且至少多一个新的边。也就是说理论上最多会需要 轮。

那如果我们能将每次增广的时间复杂度降到 就可解了。

那很显然，如果我们使用 bfs 版的匈牙利算法，那么他每一次都是 的，然后再带上至多 次增广（ 个节点肯定已经有匹配了），总复杂度 。

代码如下：

然后我们偶遇了一个 trick: 抓大放小，rt。

其实这个名字起的听生动的。说白了，就是给更重要的那部分提权，使得它的影响力严格优于次要部分。

在这道题中，我们需要在满足最大匹配的前提下使得换位置的元素个数最少。

我们令没有交换位置的匹配权值大 ，并且原先匹配的贡献乘上 ，这时候对最大匹配的影响至少为 ，而总的不交换的贡献严格小于 ，从而优先满足最大匹配，然后满足最少交换。

最小树形图

主要讲三个东西：朱刘，tarjan，堆优化朱刘。

朱刘算法

朱刘算法思路很简单：不停的找环，把环缩成一个大点，然后接着找，直到形成一个 DAG。

更大的思路是除了根节点，每一个点尽可能选取最小的入边。显然在一个环中，我们不能直接抛弃最大的边，而是将连向这个环的那个边减去环上随后的那个边的权值。

也就是在反悔贪心。同时你也就可以反应过来为什么不能暴力选最大边。

所以你要是暴力模拟这个过程的话，你就得到了朱刘算法。代码如下：

tarjan/堆优化朱刘

他们的优化思路很简单，就是堆优化。

那么 tarjan 是怎么去求解的呢？它分为 收缩 与 伸展 两个过程。说白了就是先将整个图按照强连通分量缩成一个点，然后再根据记录的信息给把树重新建出来。

收缩怎么收缩呢？我们每一次任意选一个在堆中没有入边的的节点，并将它的最小入边加入到堆中。如果新加入的这条边使堆中的边形成了环，那么将构成环的那些结点收缩。我们不停的收缩，直到整张图被收缩为一个节点。

堆中的边总是会形成一条路径 ，由于图是强连通的，这个路径必然存在。我们每一次选一条最小入边 。如果 不在 中就将 定为 。如果在就形成了一个环。我们将这个环缩掉，显然还在最后。我们接着处理这个点就完了。

当然了，收缩的过程中需要记录一些信息。伸展过程是相对简单的，以原先要求的根节点 为起始点，对 到收缩树的根上的每一个环进行伸展。再以 的祖先结点 为起始点，将其到根的环展开，直到遍历完所有的结点。

一种实现：

堆优化朱刘相对而言可能会更好理解一点，真的就是给朱刘套上了和 tarjan 类似的可并堆优化。但是要注意处理指向环内的边。这些边对 tarjan 正确性没有影响，但是对朱刘有影响。给出完整的代码如下：

见的不多，而且目前来看遇到了基本上就挺板的，不再多说了。

仙人掌与圆方树

模板题显然就是一个狭义圆方树求仙人掌上两点之间的距离的板子题。

先说一下什么是仙人掌：仙人掌就是一种特殊的图，满足每一个边最多在一个简单环上。

我们会使用倍增 LCA 和树上前缀和来快速的求解树上的两点之间的距离。那如果我们可以将这个图转变成一棵树的话是不是就做完了？狭义圆方树就干了这么一点事。

那我们想一想这个圆方树都要处理一些什么呢？显然，成环的地方就是我们要重点考虑的。正是这些环，使得原先的图不是树。我们考虑如下结构：

肉眼可见的，我们通过添加一个点使得一个环变成了一个菊花一样的东西。我们处理完后一定是一棵树。而树上除了根以外别的点都一定是有父节点的。只要我们指定一个圆点为根节点，那每一个这样的环都会有一个最靠上的节点。

我们把这个节点视为这个环的起点，像任意方向绕着环转一圈，并把每个点的“距离”标记为第一次遇到他时走过的路程。接下来，我们把环的起点到这个环的方点的边权设置为 ，把这个环的方点到其他点的权值设为本环的起点到那个点的最短路的长度。

这意味着我们还需要处理这个环的长度。因为最短路是这个点的“距离”和环长减去“距离”的最小值。就像这样：

建出来了树了之后，分成两种大的情况：

第一种：两个点的 LCA 是一个圆点。这种情况相当的好，答案就是两个点在树上的距离。

第二种：两个点的 LCA 是一个方点。这意味着这两个点不停往上跳，最后跳到了一个环的不同的两个点上。这时候我们要处理出二者在环上的最小距离。于是我们之前记录的信息就发挥作用了。两个点之间有两个不同的种路径，一种是按照“距离”的行走方向的那段弧，长度为二者的“距离”的差，另一种是走另一段弧，长度是环长减第一种的长度。

至此，狭义圆方树求仙人掌上两点之间的距离讲解完毕。代码如下：

同学提出了一个问题，我觉得有必要讲一下：一个点有可能会在多个环里，为什么我们不需要记录这个点在每一个环中的“距离”和环长？

我们想一下我们询问的过程：首先如果 LCA 就是圆点的话那没什么影响，如果是方点的话那才会用到“距离”和环长。但是很显然，一个环的起点是骑在这个方点的上面的，也就是我们永远也不会用到一个环的起点在这个环上的信息。

而很显然，我们在建树的过程中，一个点永远也不会成为多个环的“终点”，而且最后一次处理这个点就是在他是“终点”的那棵树上。故不需要记录一个点在每个环上的信息。

那么，一个比较常见的应用就是圆方树上 DP，虽然我们不一定要把树真正的建出来。如题。

面对仙人掌的题，我们最基本的思路就是转化成树上问题求解。而很显然仙人掌本质上就是一棵树上面挂了一些边不相交的基环。

先看第一道题：没有上司的舞会。没错，这就是同一道题，只不过仙人掌上没有环而已。

为什么思考这个问题呢？因为这就是在推最基础的 DP 式子。显然：

。

再看第二道题：城市环路，不过请自己弱化一下，每一个点的人流量都是 。没错，这就是同一道题，只不过仙人掌上有且仅有一个环而已。

那我们想一下面对基环树时的套路呢？先随便选择两个相邻的点，指定他们的状态，然后进行 DP。

现在看回这一道题。现在“树”上有一堆子基环了，我们怎么办？

仙人掌的典型套路：把每一个环拆出来，逐个击破。剩下的非环边正常处理就完了。

所以面对基环树 DP，思考大抵是有点套路的：思考树上怎么做，思考怎么处理基环，套仙人掌找环处理环的板子。

代码如下：

数据结构

树状数组

思路：先引入一种运算：lowbit。其意思是取某一个数二进制下最低的为一的位的值。

实现也非常简单，。

背后的原因也很简单，首先由补码反码的知识（卡常的知识）可以知道 。然后，我们又知道一个数的最后一个 后的零取反后全变为 ，而这个数变为 。加完一后从这一位起往后都与原数相同，保留，以前的（不含）一定不同，与出来一定是 ，求出来就是 。

这时候，我们每一次修改的时候，从修改起始位置 开始，每一次先将修改位置按照所需修改方式（如加），然后将 加上 ，并继续修改，直到 （ 为修改值域）。我们每一次查询的时候，从查询起始位置 开始，每一次先将 按指定操作方式（如加）将当前位置的值算到 头上，然后将 减掉 ，并继续修改，直到 。能运用这个快速的求出一个序列的带修前缀和或者序列某一位之前比这一个数小的数的个数等。

为什么这是正确的呢？

假定我们修改了位置 的数，然后我们在 位置查询，分两种情况： 或者 。当 时， 的修改路径显然不与 相交，不会被统计到，显然是正确的。

当 的时候，似乎有一点难分析，我们再分两种情况：二者最高二进制位对齐或者不对齐。当二者没有对齐时， 一定是位数更少的那一个（）， 是位数更大的哪一个。

那么 的修改路径一定是 ，其中 其实就是最小的 ，使其满足 和 。正确性显然，因为除非一个数的二进制下的 全部在高位，否则 不可能使其进到更高位的数。而一旦进到更高位，就只会有最高位的一个一，每一次都相当于乘二。

的查询路径一定是 。正确性应该都知道，就是在从低位向高位删 ，最后一定会来到 ，这也是和修改路径唯一的交点。因为 与 的二进制位最初位数不同，所以 。又因为 对于此时的 相当于乘二，所以修改路径会唯一一次的经过查询路径，没有多统少统。

那么当二者对齐的时候呢？

很简单，从头看到脚趾尖，从高位向低位看，找到第一个不一样的位，这个时候一定是 为 ， 为 。那么，再分两种情况：此位之后 还有为 的二进制为，或者没有。

当没有的时候， 一直用 减去低位就能得到 。

当有的时候， 仍然一直用 减去低位，直到这一位（不含），然后 一直加，直到这一位变成 ，最终就能达到相同的数。

最后我们就只需要证明一下这个数不会被重复统计就行了。

首先，由上面的方法可以知道，这两个路径一定有一个交点。这时候我们找到这个交点的最后一个 ，对其进行思考：这个点对于 而言可能是怎么来的？对于 呢？

假如说最后一个一在第四位，形如 ，那么对于，可能的来源有 ，对于 ，可能的来源有 。其中，又因为 的情况已统计，所以没有重复的。严格证明：

我们注意到因为 改变过程中只会删掉 ，不会增加 ，因此 原数中一定有这一位是一。如果 原数就是这样的话，那么因为 与之相同的情况已经统计，忽略。又因为 每次的修改是加上 ，所以从最后一个 起所有连续的 都被改为零，这些 前面的第一个 改为 。所以，若 原数在这一位和更低位都有的话，那么一定不会在这里相交。所以， 这一位一定为 （相交前）。这样，相交前一定不会有交点。

相交后， 加上 只会在更高位的地方发生增长，而 只有可能在更低位的地方发生增长，二者互不相交。正确性到此证毕。

（注：上面是我在自己的远古博客中扒拉到的证明。不保证严谨。）

他能直接维护的操作时单点加，求前缀和。实现这两个操作的代码如下：

注意这份代码维护的是前缀和。总之，我们最需要记住的是这个东西的时间复杂度是极小常数的 ，有传闻说这个东西是 当 跑的。实际上没有那么夸张，不过确实飞快。这个东西算是最基础却极其好用的数据结构。后面还会多次遇到。

线段树

线段树是 OI 当中最常用的数据结构之一，务必认真掌握。接下来讲解的是比较常用的多种线段树及其变体，大致按难度排序。下面主要讲一下普通线段树的结构。

不失我个人风格的，我喜欢把线段树画成线段构成的树。如下：

哈哈，十分的生动形象。线段树上的每一个“线段”维护的就是这个区间内的信息。比如区间和，区间最小值，区间极差，等等。总之你需要维护什么就往这上面去堆。

不过呢，他没有那么的万能，至少你想要维护的信息要么可以简单的合并，要么可以直接标记永久化。总之还是有一些限制条件的。下面针对各种线段树进行相关的介绍。

序列线段树

就是针对序列建立一颗线段树，用来维护各种各样的操作。一个最经典的问题就是动态维护最大连续子段和。这里我们主要是来说一下怎么去思考线段树如何维护这类问题。

我们思考一下，一般来说像这种比较直接的问题都会选择把答案给维护出来。所以区间上指定是要记录最大子段和的。

但是仅仅这样是的话我们发现是不行的。最大的问题出现在信息合并上。我们发现仅仅记录区间的最大子段和的话我们是没有办法向上面的区间合并信息的。

因此，一般来说，我们会需要记录更多的信息来辅助合并其他的信息。比如说，为了最大子段和，我们会需要辅以区间和，前缀最大子段和，后缀最大子段和。

确实就能维护了！所以这一次我就只讲了一点基础的思路：堆信息。显然这是一种一些情况下可行的思路。

这道题核心代码如下：

动态开点线段树

我们注意到在上面的代码中，我们一开始就把线段树直接给显式的建立出来了。这样子的空间复杂度可以被证实为是 的。事实上，如果只考虑 ，其上界是不超过 的。

不过如果我们的序列足够的长，达到 级别的话，那么这种空间复杂度仍然是无法被接受的。我们思考一下，空间大部分被浪费在了那些可能永远不会被更新的节点上。比如说最开始时所有位置的值都是 的话，并且我们保证修改次数在 左右，其实实际有效的节点大约是 个。

因此，我们采用的策略是我们不把整颗线段树显式的建立出来，而是用到哪里建到哪里。每一个节点，我们需要再多记两个信息：左右儿子的节点编号。修改时递归下去，没有点就建点并动态初始化即可。

这个技巧需要注意的就是注意“空”儿子。这些节点往往信息特殊化，可能需要在合并的时候特殊处理。

值域线段树

值域线段树，顾名思义，就是在值域上建立的线段树。因为值域范围通常是比较大的，所以我们常用的技巧是离散化强制压成序列线段树或者直接动态开点。如果不强制在线的话通常前者会是更好的选择。一个非常好的应用题是【模板】普通平衡树。

哈哈，听起来很超纲，不过你只需要会值域线段树以及线段树上二分。

所谓线段树上二分，其实也不过就是根据当前节点和子节点存储的信息，决定答案在左右哪个区间里，直到叶子节点或者想要的点。

插一篇用值域线段树详讲这道题的的题解。

可持久化线段树

可持久化，听起来非常的高级。可持久化指的是支持对历史版本的维护。具体地说，我们发现常见的数据结构实际上只维护了最新状态，然而对于一些特(du)殊(liu)情(ti)况(mu)，我们会需要维护出某一个东西在历史上的状态。

比如说有一个东西叫做可持久化数组，要求就是支持基于任意历史版本的修改，以及对任意历史版本的查询。

一个非常朴素的想法是每进行一次修改，就新建一个数组，存储出新的版本。

我们考虑对这个思路进行优化。注意到一件事情：单次的修改其实只涉及到了一个位置。也就是说剩下的 个位置的值全部是多余的。我们思考有没有办法尽可能的继承上一个版本的信息。我们对数组直接建立线段树如图：

其中蓝色标记的是修改的位置。然后注意到了一件事：其实除了修改位置到祖先的节点意外，其余的节点维护的信息完全没有变化！

那么我们考虑可不可以“偷换”子结点呢？我们表面上继承的是信息，实际上直接继承子结点的编号就行了，如图：

也就是说，我只新建发生更改的节点，其余的直接继承就行。这就是可持久化线段树的最主要的思想：可以继承就继承。也就是在尽可能的提高被回收的节点的数量。

这是针对序列的一个比较板的形式，实际上一般也不会直接这么考。你能见到的更多是他的应用，比如可持久化并查集，可持久化平衡树什么的。或者是可持久化值域线段树。

举个例题：给定一个数列，多次询问 中 的数的个数。强制在线，不然就可以被绕过去。

我们针对值域而非序列建立一颗可持久化线段树，并将序列中的 个数对应的线段树视为第 个版本。注意到实际上 区间对应的线段树就是 版本的线段树和 版本的线段树对应位置“相减”的结果。这是在线的单 做法。

线段树合并

线段树合并一般来说是针对动态开点权值线段树的。正如其名，他会将两棵线段树的信息合并到一棵上面。例题就放模板题吧。

首先我们注意到，单次发放粮食是在路径上发放的，结合这道题“强制离线”的情况，不难想到使用树上差分而不是树链剖分，从而简化问题。

接下来，我们注意到，每一个点都必须累计子树内所有的信息之后才能够统计答案。也就是说我们会需要一些较为高效的方式合并子树内的信息。事实上，对于这道题，DSU on tree 是正确的，不过我们暂时不考虑。

我们可以考虑将一个位置插入一份 类型的救济粮视为在这个位置的权值线段树的 位置 ，将合并子树内的信息视为生成一颗对应节点信息合并的权值线段树。于是转化为线段树合并题。

我们考虑这样子去合并：如果这个位置两棵树都是有值的，那么就先去合并子结点，然后再上传合并后的子结点的信息。否则保留有值的那一颗的节点。如果都没有值的话，那显然是没有影响的，直接传一个空节点上去。代码如下：

不难注意到，单次合并的时间复杂度是和重合节点的个数成正比的。

那么注意到，如果原先有 个插入了 的线段树，那么在合并的时候这个节点链只会被合并一次，所以总的时间复杂度是 的。

对于更加一般的情况，一般需要从单次合并的时间复杂度入手进行分析。比如说在这道题中，如果你选择了线段树合并，那我只能追忆你了。

下面是华丽的图：

线段树分裂

有了线段树合并在前面，线段树分裂就是比较好理解的。而且非常类似 Treap 的分裂。

具体的来说一般分成两类分裂：按值分裂和按大小分裂。不过实质上都是差不多的，就只在实现上有细微区别。一般来说只在维护一些可重集上的问题，或者序列的分割等操作时才会有点用。模板题在这里。

分裂，顾名思义，就是把一棵线段树按照一个线分裂为两个线段树。也就能和可重集或者序列的性质对上。

具体的来说，我们一般会传进去分割线、当前节点、左右线段树的引用点。因为两个子节点总有至少一个是被完全包含在左区间或者右区间，因此包含部分占优的那一边可以选择继承原树，劣势的一方再去建立新的节点。分裂完之后再重新上传信息即可。代码如下：

下面又是华丽的图，按照大小分割：

ZKW线段树

很神奇的卡常用的线段树，但是支持面远远比不上普通线段树。

思路就是更改递归为循环。我们可以注意到，在线段树中，，因此，我们维护一个数组，使其也满足这样的性质，每次循环向上更新信息，就完成了。

查询的时候我们从区间的左右部分的端点外的一点开始操作。对于一个端点，当我们向内跳的时候，统计右儿子的贡献，当向外跳的时候，不统计贡献，直到两端点重合。

但是区间修改使用标记永久化，无法维护标记有顺序要求的情况。

参考代码如下：

并查集

普通并查集

并查集要维护的操作主要就是“合并”和“查询”。具体来说，他要能够支持将两个集合合并，并查询每一个元素在哪一个集合，比如判断二者在不在同一个集合中。

不难想到我们可以用类似于树的结构来实现这一点，具体的来说，我们要合并 所在的集合的时候，我们找到这两个集合的代表元素 ，并将其中一者的父节点设置为另一个。

但显然这样做如果给你整成链状的你就炸了，因此我们有诸多技巧来维护其时间复杂度正确。

第一种是路径压缩，也就是每一次查询完某个节点之后，我们将这个节点到他的代表节点这一条链上的所有节点的直接父节点设为代表。这样做时间复杂度均摊是 的。显然不是特别优。如果你再把他们按照大小合并，也就是将大小更小的那一坨的父亲设为更大的那一坨，时间复杂度进一步降至 。其中 是反阿克曼函数。

实际应用中，根本没人去卡那个 ，所以更常见的情况下你并不需要按大小合并。

还有另一种是按秩合并，也就是树高更低的合并到树高更高的上面。时间复杂度显然是 的。

扩展域并查集

又名种类并查集，思路就是拆点。举食物环为例题。

在这道题中，每一个生物对应有三种状态：是 A/B/C 类生物。于是我们将每个生物拆成三个点，比如说第 个生物就会被拆成三个不同的点 ，其中 表示 生物是 类生物这个陈述为真。而我们将并查集视为一种等价关系，即如果 在同一个集合内，我们就认为这两个命题要么都成立，要么都不成立。

那么对应到这一道题，如果两个生物是同类，则 ，， 应该分别进行合并。显然判断条件是 不能相互啃食，比如 或 等共计 个条件。二者相互啃食的类似，不再赘述。

可以给出核心代码如下：

权值并查集

这类并查集会需要维护多维的信息，比如和代表的实际距离。例题。

一般情况下，我们会考虑在重定向父亲的时候先去除父节点造成的影响，然后在路径压缩的过程中再逐步去合并信息。比如说当有一种信息是针对整个并查集改的的时候，我们会在合并的时候先将合并者的信息“减去”被合并者的信息，然后再在后面恢复过来。当然了，这个例题体现不出来。

一定要注意路径压缩时对信息进行合并的时候要记录好原先的父亲，不要随意拿着新的“父亲”去更新信息。

可以给出核心代码如下：

莫队

这绝对称得上是离线算法中的代表之一。话说，彼时的 界 问题并起，而我们的暴力却不能骗到太多分，于是 高手圈内流行起了一种快速处理离线问题的算法，并由莫涛整理，这种算法便被称之为莫队。后人便在此基础上加以拓展，统称为莫队算法。

算法的实现就是询问区间依靠 指针反复横跳。他要求我们能够在较优的时间复杂度内（一般为 ）用 的答案及状态转移出 或 的答案及状态。这时候，我们通过一定的方式找到一个较优的询问序列，使得其左右横跳的次数较为少。

这时候莫队的神奇重排询问方式发挥了作用。首先我们先这 个点顺序平均分成 个块，然后询问间排序时以左端点所在的块编号为第一关键字，右端点为第二关键字。这时候，右端点右移距离不超过 ，左端点移动次数在 的级别控制内，均有不超过 的理论常数（像黑塔那样左右乱滚）。于是总复杂度在 。

普通莫队

显然，上面的就是普通莫队。

以袜子为例，核心操作就是这样的：

特别注意，我们应尽量保证区间长度不为负，所以我们总是先扩展再收缩。

带修莫队

核心思路就是加上一维时间戳，因为 同在 的区间内，所以我们把 的排序方式强加在 上，然后 按照原来 的排序方式升序排序。当块长取 时时间复杂度为最优的 。但是一般情况下 同阶，所以时间复杂度常被视为 。

带修莫队有他的局限性。只支持单点修改，时间复杂度也已经只比暴力优了 ，可能要卡常。

回滚莫队

回滚怎么滚？为什么要滚？问题很简单，有的信息在增加或删除的时候很难在一个能接受的时间复杂度内处理出来。于是，我们就只让他扩展。

具体的，我们暴力处理完块内的询问后，块间的我们让他的左端点固定在 的位置，保持右端点单增，每到一个询问，记录当前的状态，让左端点扩展，到之后记录答案，然后快速滚回到 。

可以参见野史的研究的代码。

树上莫队

经典的序列问题上树。处理方式无非就两种：把树拍成序列；重链剖分吃掉这棵树。很显然，对于莫对这种喜欢像黑塔那样左右乱滚的神奇算法来说，第一个方式会更友善一些。

最终，我们选择了欧拉序，即进子树记录一次，出子树记录一次。这样子，我们可以通过一个点在序列中出现的次数轻松的知道他到底在不在序列上。

一般的，我们会将其拆成 和 两条链来处理。由于欧拉序的特殊性，对于不满足一者在另一者的子树内时，我们需要记录 。

然后就是类似于普通莫队的思路了。下面给一个树上莫队的代码：

笛卡尔树

笛卡尔树是一种二叉树，每一个节点由一个键值二元组 构成。要求 满足二叉搜索树的性质，而 满足堆的性质。一般我们会需要构造一个笛卡尔树，编号为 的点权值为 ， 为给定的值。一般用栈解决。方法如下：

我们先按照下标顺序依次加入这棵树中，显然，为了维护二叉搜索树的性质，这个节点势必会在树的右链上。

这时候我们维护其堆的性质就行了。从下往上比较右链节点与当前节点 的 ，如果找到了一个右链上的节点 满足 ，就把 接到 的右儿子上，而 原本的右子树就变成 的左子树。

复杂度线性。可能视情况会需要树上 ，四毛子等。

树套树

首先给出警告：树套树时空常数大，代码复杂，一定要静下来调，线段树中不要记录当前节点的区间端点，在函数中下传！

其实修正一个对树套树的认知错误：树套树实际上只有最内层在维护实际有效信息，外层只是为了减少内层维护次数，从而降低复杂度，而不做信息的合并。

在这基础之上，就不容易出错了。主要补充一些技巧。其中第二个板块有线段树套平衡树的参考代码。接下来讲一下相对好写而且支持面较广的树状数组套线段树。

这里有你没写完的东西，杂鱼...

线段树二分/树状数组倍增

前者就是线段树上二分。因为线段树是分治型结构，所以复杂度单 。方法就是在每一个节点选择往左/右子树走。

后者如其名，因为树状数组是倍增型结构，所以复杂度单 。方法就是跳 个， 越来越小。这时候，前面的贡献不会被重复统计，达到效果。

多树二分

不难注意到，在树套树模板题中，我给出了如下代码：

那么请看第 到 行，这一部分就是为了防被卡。仔细看会发现这个操作是 的。这时候就需要多树二分了。

多树二分，一句话说，就是将会涉及到的线段树树上的节点给全部放一起，然后一起二分。这时候，节点个数是 级别，二分是 的，整体双 。以 lby 的代码作为实现思路：

严格次小生成树

还挺简单的，能直接口胡出思路来，就是建出最小生成树，然后在上面换边。只涉及到了倍增和最小生成树相关的。给出相对简短的实现：

整体二分

正如其名字，我们将所有的询问放到一起来二分，这样可以节省中间重复的判断的时间。思路很简单，结合题目去想一下能不能高效维护就是了。

例题核心代码：

只是题必须满足以下性质：

  1. 询问的答案具有可二分性
  2. 修改对判定答案的贡献互相独立，修改之间互不影响效果
  3. 修改如果对判定答案有贡献，则贡献为一确定的与判定标准无关的值
  4. 贡献满足交换律，结合律，具有可加性
  5. 题目允许使用离线算法

陈丹琦分治

CDQ 分治其实更像是一种思想。CDQ 的经典例题处理的是三维偏序问题，即满足 的整数对 的个数。

这个东西，一看就可以 KDTree（大雾）。

显然不优，CDQ 可以做到 。

核心思路就是先按照第一维排序，随后归并排第二维的序列。归并的时候，左部点仍然满足 比右部点小。此时我们依次归并 ，当 来自右部点是计算比该点 值更小的已归并的数量之和，这可以用树状数组快速维护。

求解完成。模板题核心代码：

可以求解类似动态逆序对，二维数点等的部分问题。

但是这只是非常狭义的 CDQ 分治。我们现在要去研究其核心思想，也就是对于更广的一类题目，我们到底怎么处理：

从上述过程中，我们可以窥见 CDQ 的核心思路。假设现在我们要求出 的贡献，那么我们将其分成两半 和 ，然后统计 对 的贡献。

事实上，中间贡献的计算不一定是像三位偏序那样的简单的数据结构，它可以是线段树，平衡树，kd-tree，甚至是另一层 CDQ 分治！

一个典型的例题是四维偏序，但是我们换一个略有挑战性的TATT进行讲解。

在经典的三维偏序中，我们每一次二分的时候可以视为将左区间的 拍扁成了 ，右区间的拍扁成了 。在保证 的前提下，只有 能对 产生贡献。

在四维偏序中，我们可以使用类似的思路：我们在第一层将 拍扁成 ，然后在第二层将他进一步拍扁成 ，然后只统计当 时 对 的贡献。仍然使用树状数组。

下面给出TATT中的 CDQ 部分的参考代码：

线段树分治

老经典，老好用的一个算法了。

线段树经常用来处理在某一段时间内修改的不易回退的问题。比如动态图的二分图判定，也就是这道题。

二分图判定有多种方法，常见的有染色法和并查集法。染色法因为图是动态的而难以维护，反观并查集则有较多的变种，因此我们选择从并查集判定二分图的角度入手解决这道题目。

问题来了：修改是一段时间内的。加边好处理，但是删边呢？而且万一没有加成功，那你删边不是很难处理吗？

这就引出了线段树分治的核心思路：既然删除难，那我是不是可以选择不删除？

说起来简单，做起来也似乎不难。我们考虑对时间轴建立一颗线段树。每一个叶子节点对应一个时间区间内全部都有的修改操作。最后在求解的时候我们记录好当前位置的状态，然后递推下去求解，回溯时将做的修改无效化。

没错，这就是线段树分治的核心玩法。具体流程如下：

  1. 对整个时间序列建立一颗线段树。
  2. 将操作插入线段树，插入的区间就是操作有效的区间。
  3. 所有操作插入完成之后，从根节点开始递推求解。
  4. 每一步，现将当前的状态记录好，然后递推求解下一层，回溯时恢复状态。
  5. 到达边界条件时或有查询时记录答案。

其中回溯时恢复状态，常见的做法有直接存储状态，回来时覆写和存储修改，回来时撤销两种。

显然在这道题当中，我们只能选择第二种。那你又问了：你这不是还要撤销吗？难撤销的问题没解决啊！

其实我们不难发现，如果某一次我们合并失败了，那也就意味着这一整个时间段内这个图恒不是一个二分图。因为同一时间段内不涉及撤销操作。

因此我们可以使用可撤销并查集依次进行合并，合并成功就记录一次合并操作，准备后面撤销。如果合并失败就直接将当前时间段内的答案标记为非二分图，并撤销当前时间段内所做的所有合并操作，直接回溯。

这其实并不麻烦，代码不算特别短，但是很好理解。代码如下：

重链剖分

重链剖分是树链剖分中最强大也最常用的一种。重链剖分是这样的：

对于每一个节点，我们选出他的一个儿子，满足以这个儿子为根的子树大小不比别的子节点小。我们称这个儿子为重儿子。其他的我们称为轻儿子。连接重儿子和父节点的边称为重边，其余的称为轻边。这时候，一个极长的只由重边构成的链称为重链。显然一棵树会被剖分成许多的重链。

随后我们使用数据结构对重链进行维护。一种常见的做法是使用线段树。不过这要求链上的节点的编号是连续的。我们按照优先遍历重儿子的方式对整棵树上的节点重新标号为其 dfs 序。这时候同一重链上的节点的编号连续，同一子树内的结点的编号连续，因此我们可以快速维护部分对路径或子树进行修改或者查询的操作。

有点抽象，还是举个例子。比如模板题，他要求维护子树加，子树求和，路径加，路径求和。确实模板，我们主要说一下路径的维护方式。

树上的任意一条路径本质上都是一堆重链的部分被一些轻边串了起来，同时也是 和 串起来。因此，我们可以考虑通过不停的跳重链的方式维护路径信息。

具体的，如果 还不在同一条重链上，我们就选择链顶深度最大的那个节点去跳，先合并链顶到那个节点的信息，然后让那个节点跳到链顶的父节点。当 到了同一个重链上之后，我们就可以直接合并 的信息。

代码其实挺简单的，但是我们还没有证明时间复杂度。

我们发现一个性质：我们每跳一次轻边，以当前节点为根的子树大小至少能够 ，因为有重儿子压着你的嘛。也就是说，一个点只要是在向上跳，那就至多只能够跳 次。跳到 上其实也是同理的。

所以单次操作时间复杂度就是 的。核心代码如下：

长链剖分

虽然和重链剖分一样都是树链剖分的一种，但是面对的主要问题却很不一样。长链剖分主要是解决一些和深度相关的 DP 问题。长链剖分是这样的：

定义长子节点表示其子节点中子树深度最大的子结点。定义短子节点表示剩余的子结点。从这个结点到长子节点的边为长边。到其他轻子节点的边为短边。若干条首尾衔接的长边构成长链。

它本身并不是很适合维护链修改操作，毕竟他最多会跳 次短边，远远劣于重链剖分。但是对于深度相关的 DP 问题却有着很大的优化。比如这道题：

DP 式子其实非常好想，难就难在转移。你可以通过线段树合并等等复杂的技巧去维护，但是这是不必要的，我们可以用长链剖分用简短的代码做到线性复杂度。

具体的来说，我们让一个节点直接继承长儿子的 DP 数组，并在前面插入一个数 ，表示在相对深度为 的位置有且仅有一个节点，然后暴力合并所有短儿子的 DP 数组。做完了。

没错！做完了。我们分析一下时空复杂度。

首先对于每一个长链，我们仅在链顶的时候被暴力合并一次，而且显然有效的位置最多只会有其长度那么多个，因此合并的时间复杂度是 的。空间呢？我们发现我们可以通过指针预留空间的方式，让一整个链完全基于同一个数组进行修改，不同的链也可以通过相应的偏移给别的链预留足够的空间，从而空间也是线性的。

代码如下：

有的时候不得不佩服一下发明这种简洁美丽的算法的人。这才是数据结构的美之所在。

平衡树

平衡树本质上多是一棵 BST，但是将值顺序插入 BST 会得到链，所以平衡树要通过各种技巧维护 BST 的树高。最常见的操作是旋转，也就是调整父子关系的同时维护 BST 的性质。

这里介绍两种最为常用写的平衡树和一个替代品。一个是 Splay，一个是 FHQ-Treap。主要会围绕两道模板题进行讲解。

Splay

Splay 采用的是旋转的思想，而且比 Treap 本体的旋转操作更为单一，只有上旋操作，就是顶替父节点。

首先，我们会需要一些最基本的辅助操作。一个是 bel，用来判断某一个节点是不是父节点的右子节点。一个是 pushup(pup)，是用来更新节点信息的。

接下来是重头戏：旋转操作。这个是用来保证时间复杂度的。作为一颗 BST，旋转操作需要保证中序遍历不变，而且节点的信息能够及时更新。

Splay 中，最基础的旋转操作是单旋，将是让某一个节点 向上顶替他的父亲 。细分的话其实可以分成左旋和右旋，跟 Treap 似的，如图：

但是我们要善于发现操作的共性。这两种旋转本质上都在做如下步骤：

  1. 找出父节点，爷节点，与父结点方向相反的子节点，也就是这样（注意严格区分方向）：

  1. 在父节点原先挂自己的地方挂上那个子节点，调整相应父子关系，合并信息。
  2. 在自己原先挂子节点的地方挂上父节点，调整相应父子关系，合并信息。
  3. 在爷节点原先挂父节点的地方挂上自己，调整相应父子关系，合并信息。

写出来代码就长这样：

还没有完，如果你就一直这样把一个节点旋上去的话，时间按复杂度是不对的。最简单的一个例子就是一条方向相同的链，旋完之后正好变成了换一个方向的链。

所以我们引入更加神奇的双旋。也就是说我们两次两次的转。如果本节点到父节点的方向和父节点到爷节点的方向相同，就先转父节点。再转自己，否则连续两次旋转自己。我们发现这样之后，自己一定有两个子节点，分别是原先的父节点和爷节点。感觉树高似乎就有保证了。

接下来是 Splay 中最核心的操作：splay。它的作用是将一个节点旋转到另一个节点下，或者直接转到根。在这一步，我们就是要不停的调用双旋，直到转到想要的位置。也请请务必保证每次向下访问节点后，都进行一次伸展操作。这是它的时间复杂度能够得到保证的关键步骤。严格证明需要势能分析，而且较长，这里不做阐述，具体的可以参见 OI-wiki 上的证明。代码如下：

最基础的操作就搞定了，剩下的就是针对题目的操作了。具体参见以下的对普通平衡树的代码：

没有完，splay 树的结构非常灵活，它也可以用来处理区间翻转类的问题。但是暂时没有去研究，毕竟在这方面他的表现比不上 FHQ。可以在下面的第一个网址找到动态演示。

https://www.cs.usfca.edu/~galles/visualization/SplayTree.html

https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

FHQ-Treap

FHQ-Treap 又称无旋 Treap。从名字就能够看出来这是一种不带旋转操作的神奇平衡树。但是这个名字看着又眼熟又觉得怪怪的？没错，Treap 是 Tree 和 Heap 的合成词。这样一颗树有两个核心键值，一个是我们 BST 维护的本体信息，一个是用来保证树高的数值。

Treap 满足第一个键值的中序遍历是有序的，也就是满足 BST 性质，第二个键值父节点大于任何一个叶子节点，也就是满足堆性质。

他的思想也很简单：既然在随机数据下 BST 的期望树高就是 的，那我要是引入一个随机的键值，是不是他的期望树高也差不多就是 的呢？没错，他用做堆的键值是随机生成的。

显然前面介绍的 Splay 的旋转操作可以维护这两个键值的信息，那他是怎么把旋转操作抹去的呢？

通过分裂与合并！这两个是 FHQ-Treap 的最核心的操作。分裂时按照第一键值的大小分成两部分，合并时按照第二键值的大小维护堆性质合并成一部分。

其实差不多就讲完了，剩下的就可以看代码了。毕竟他的核心思路相较于 Splay 简化了不止一点。

分裂：

合并：

其实和线段树的分裂和合并是比较像的。总的代码如下：

不仅如此，因为他在合并的时候完全不关心第一权值的大小，分裂的时候也可以按子树大小进行分裂，所以它可以快速维护区间位移，翻转以及常见修改等的问题。效率也比较高。

按子树大小进行分裂本质上就是将区间裂成了两半。其中第一半的大小完全可控。因此区间的所有操作都可以认为是将区间分裂出来，打上标记之后再放回去。其实没有特别本质的差异。对于一个稍微复杂的题的代码如下：

李超线段树

要求在平面直角坐标系下维护两个操作：

  1. 在平面上加入一条线段。记第 条被插入的线段的标号为 。
  2. 给定一个数 ，询问与直线 相交的线段中，交点纵坐标最大的线段的编号。

我们发现，传统的线段树无法很好地维护这样的信息。这种情况下，李超线段树便应运而生。

区间修改，最常见的办法就是给每个节点一个懒标记。对于每个区间，维护在 处取值最大的直线的信息。

现在我们需要插入一条线段 ，在这条线段完整覆盖的线段树节点代表的区间中，某些区间的最优线段可能发生改变。

考虑某个被新线段 完整覆盖的区间，若该区间无最优线段，则该线段可以直接成为最优线段。

否则，设该区间的中点为 ，我们拿新线段 在中点处的值与原最优线段 在中点处的值作比较。

如果新线段 更优，则将 和 交换。那么现在考虑在中点处 不如 优的情况：

  1. 若在左端点处 更优，那么 和 必然在左半区间中产生了交点，递归到左儿子中进行插入；
  2. 若在右端点处 更优，那么 和 必然在右半区间中产生了交点，递归到右儿子中进行插入。
  3. 若在左右端点处 都更优，那么 不可能成为答案，不需要继续下传。

由于仅有一个交点，所以两边子区间最多会递归一个。复杂度 。但是需要注意，因为每一次我们都需要对全覆盖的区间都进行修改，而这样的区间是 级别的，因此单次修改的复杂度为 。

查询 答案时，从根走到 节点记录的所有最优直线在 时取值的答案极值即为所求。这里是运用了标记永久化的思想。查询的复杂度就为 。

特别需要注意，对于不优的三种情况的讨论中，如果二者在端点同样优，那么一定要视为 更优。这样才能保证对于两个重复的线段不会一直走 操作，从而导致时复错误。

核心代码如下：

Q1:为什么一定要在路径上取 而不是一直走到底，返回最底部的状态？

标记永久化。

实际上，对于一条线段，他在中点最优常常意味着他在全局都是比较优的。尤其是对于第一次存入的区间。

也就是说，对于相当大的一部分线段，他其实是整个区间的子区间的最优解。但是如果真的更改整个子树，其复杂度退化为 。

所以说，与其更改整个子树，不如直接标记永久化，最后再在这些可能的最大值中刨出真正的最大值。

Q2:李超线段树合并细节？

其实不难想象，对于李超线段树这种有永久化标记的树，其合并方式不太一样。

不过，对于同一层，其实我们只需要将其中一个的最优线段合并到另一个当中，然后递归合并就行了。

特别需要注意一点，对于【模板】李超树合并，其时间复杂度实际上是 的。这一点可用势能分析得出。参见第一篇题解，非常玄妙。连官方题解都分析错了。

典型应用：

  1. 优化 DP，也就是动态维护斜率优化 DP 的凸包，支持任意地方插入。
  2. 李超线段树合并，主要也是优化 DP，主要是在对于整个子树的最优信息的合并。

例题：T0:P4097,省选/NOI-,模板题；T1:P4254,省选/NOI-,模板题；T2:P4655,省选/NOI-；T3:CF932F,省选/NOI-；T4:P4069,省选/NOI-。

动态树

动态树，顾名思义，这种树是动态的，可能删边或加边。 可以动态维护其中的连通性信息，路径信息，子树信息等，以模板题为例。

首先，你需要学会：文艺 Splay 树，实链剖分。

实链剖分？没见过。但是，我们可以管他叫乱链剖分，因为他确实是随便选一个儿子当成实儿子，其余的当成虚儿子。

这有什么用呢？他非常的灵活。不像重链或者长链一样改一个上面全得改。

剖分完了，然后呢？然后，我们将被一堆实边连到一起的树甩到文艺 Splay 里面，构成一颗树。

那虚边怎么办？我们采用一种神奇的方法：认父不认子！我们正好满足了高效维护虚边和只向上移动的需求。

又因为我们有一堆的 Splay 树，构成了一个森林，我们管这个森林叫做辅助树。一个辅助树对应原森林中的一棵树。

那辅助树需要满足什么性质呢？每一个 Splay 的中序遍历满足按照深度排序。这样，我们就完成了原森林到辅助森林的转化。

我发现自己常常突然就困惑一颗 Splay 怎么就能维护一棵子树的...。其实问题也很简单。永远记住一颗 Splay 树维护的是一条实链而非子树或者路径，这条链上的点深度单调递增，而且恰好就是 Splay 树的中序遍历。Splay 维护的是一条链而不是一颗树，或者一条有上有下的路径，他只管好自己的链就完了。

接下来，就是实现了。Splay树中都有哪些函数和变量呢？

首先说最基础的 pup，pud，rot 和 splay。

pup 即 pushup，将子节点的信息上传上来。这里，我们需要维护每一个节点在 Splay 中的子树中的所有结点的异或值。

pud 即 pushdown，将旋转标记下传，毕竟是文艺 Splay 嘛。

rot 即 rotate，将一个节点向上旋转，Splay 的基础操作。但是要做一定的修改。

首先，一定要严格判断父节点是不是当前 Splay树的树根。如果不是，一定不要让祖父认这个儿子，因为认父不认子只出现在虚边，而一颗 Splay 维护的是实边树。

其次，一定要严格判断子节点是否存在，不要让 有了父节点。

别的大致没有什么好说的，注意先 pup(fp) 再 pup(p)，因为这时候 已经成为 的子节点了。

splay 就是你想的那个函数，但是因为在 中只涉及到了将一个点转到当前 Splay 树的根节点这一种操作，所以省略掉了第二个参数。不过需要注意的是因为存在区间翻转，所以在 Splay 之前要先从根开始下放翻转标记然后再 Splay。

然后说一下 特有的函数。

nor 即 not_root，判断一个节点是不是当前 Splay 的根节点。判断方式很简单，看他是不是父亲的儿子，因为认父不认子。

access 是 的核心操作，它会将 在原树中到根节点的链变为实链。可是我们不是不维护原树吗？

其实我们仔细想一下，因为他们在同一个实链当中，所以他们在 access 完了之后只会在同一颗 Splay 中。所以我们只需要将路径上的 Splay 间的边设为实边就行了。

具体的，我们不停地将当前节点旋到树根，让父亲认这个儿子（原先的儿子因为认父不认子而自动降为了虚儿子）为右儿子（中序遍历满足深度递增），再将节点重定向到父亲上就完了。

swn 即 swap_node，即将这个节点区间反转。为什么会用到呢？下面会讲。

ron 即 rotate_node，将这个点到根节点的区间反转标记下传。

mkrt 即 make_root，将这个节点设为原树的根。也很简单，打通他和根节点之间的路径（access），旋到树根，区间反转。

为什么区间反转呢？中序遍历按深度递增。反转之前他只会是整个 Splay 中最下的节点，旋到树根后所有节点都在他的左子树，区间反转一下它就成为最低的节点，也就是根节点了。

fnrt 即 find_root，找他在原树中的根。我们只需要 access，splay，然后边下传标记边向左子树走，最靠边的就是根节点。

tlnk 即 to_link，就是用一颗 Splay 树专门来维护 之间的链。显然我们只需要 mkrt(l)，access(r) 之后 splay(r) 就行了。

link 就是 中 对应的操作。他就是连接一条 的边。我们只需要让 成为原树树根，然后 就行了。

cut 就是 中 对应的操作。他就是断开 的边。我们只需要让 成为原树的根，将 转到 边上，不认父不认子就完了。

剩下的两个就是对题的函数了，不用管他。这个真的需要背板子，背什么呢？这些：

如果想要背的更精简的话，可以从 access 开始自己长一个 LCT 出来。access 既要求调用前面的所有最基本的小函数，同时也是后面多是操作的基础之一，逻辑清晰而不那么容易写漏。代码如下：

应用类题单可以参见这篇博客，更底层的介绍也可以在这里看。

当然了，动态树是图论当中博大精深的一部分，和网络流类似，他也有大量的变种与维护技巧。下面将会管中窥豹，浅浅地介绍两个常见维护要求与相应的常用的应对技巧。

先看第一道题，概括为短边加连边，链加链最大。

其实 LCT 处理这种链修链查的动态树问题的话还是比较容易的。因为我们有 tlnk 操作，可以直接提取出来一条链，所以唯一的区别就是多了一个 tag，上下传的时机和翻转标记一样一样的。省略部分重复的代码如下：

但是当他要处理一些子树相关的统计的时候就没有那么容易了。比如这道题。可以简述为有加断边，改点权，查询连通子树最大点权。

事实上这一类问题的一个常见处理方式是专门设一个变量什么的统计虚儿子的信息，然后一并合并到统计子树的变量当中。

比如在这道题当中，我们可以专门维护一个 multiset 记录虚儿子代表的子树的最大值有哪些值，在 pushup 的时候和 mx[lson],mx[rson],v[p] 一起比较，动态插入删除就行。当然这也可以用两个优先队列做到相同的效果。

另外一提，像这道题的树的结构是相对固定的，我们可以用一种神奇的科技做到不带翻转操作进行增删边。具体的来说，我们可以提前指定父亲，也就是将 LCT 的相对动态的结构静态化。那么当你需要删除一条边的时候，你只需要先把他 access 并 splay 上去之后和左儿子互不认就行了。需要重新加回来的时候，就先将父亲 access 并 splay 上去，然后互认父子即可。

代码如下：

快速傅里叶变换

快速傅里叶变换还是太超模了。FFT 可以在 的时间复杂度内解决两个次数不高于 次的多项式的卷积。

首先，多项式最直观的表示方式是系数表示，但是 FFT 转而使用点值表示。对于一个 次多项式，可由 或更多个不同点的位置确定。这一点在此不作证明。

接下来，我们假定我们有两个 次的多项式 和 ，那么假设我们算出了 个点的值，分别为 和 ，那么 必过 。

就是这么一坨东西。显然，我们如果能够快速的在点值和多项式之间转化，那么我们就能够快速的求出两个多项式的卷积。问题就在于我们如何在二者之间快速转化。

神奇的地方就在于此。让我们做一个小小的变化。假设 表示 中 的偶数次方项之和， 表示 中 的奇数次方项提出 的公因数之后的式子，那么不难发现， 都只剩偶数次方项了。

这有什么呢？不难注意到，。初现端倪，我们递归此过程的话，是不是就可以做到 了呢？

似乎并没有，接下来你在求 的时候，你无法再使用正负点对来加速了，毕竟 的平方一定是恒正的......吗？

不一定是啊！你回忆了一下你不知道学没学过的复数，想到单位根正好满足这个要求。

最底层的时候我们求最底下的那个多项式（其实已经只剩单项式了）在 ，其中 取值范围为 。

那么你再观察一下，当 的时候，。也就是说，只要我们能让 是一个形如 的数，我们就能一直将这个过程进行下去。

那很显然，不足的位我们直接补 就完事了。

于是我们成功地将多项式在 的复杂度内变为了点值表示。

那么，怎么从点值变回多项式呢？

我们这样来看：FFT 实际上是快速的求出了 。那么经过一些神奇的推导，我们很难发现：。这一点可以通过直接的数论推导或者 FFT 中各步骤对应的矩阵乘法形式通过逆矩阵证得。

此时你又定睛一看，发现如果你令 ，那么 ，FFT 不就能求了吗？

因此，我们求出了两个多项式的卷积，复杂度 。

更多优化与应用在 NTT 讲。

快速数论变换

也算是为数不多的几个完全不需要掌握其所以然的算法了。可以从 FFT 那里变过来。

NTT 本质上就干了一件事：把复数映射到了整数集上，然后接着干。

怎么映射呢？原根。对于质数 ，且 ，那么原根 满足 。此时我们可以将 看作 的等价。

说白了，在模 意义下可以认为 。常见的 有 。

所以你只需要把代码中对应的那些位置替换一下就行了。

若干优化

逐步看。这是 FFT 比较劣的一个版本，模板题要跑 2.77s。

我们知道，复数的运算其实很耗时间，所以能少计算一次，尤其是乘法，会有一定的优化。所以我们将 tv * vr[i] 的结果存下来。这样就能优化到 2.65s。代码如下：

这不是重点，接下来要介绍一下非递归版的 FFT。

我们在运行的时候会不停的涉及到交换位置，导致最后算出来的东西出现乱序，根本用不了。但是如果我们预先将这些位置预先换了，是不是就没有那么多问题了？

依据这篇博客所讲，假设我们就是有 个数，那么最后 位置上的数是 二进制翻转得到的数。事实上仔细思考一下前面分流的过程会发现的确如此。

注意观察下述代码的计算 sp 的部分。这一部分就是在生成 i 的位翻转索引，仔细分析一下其正确性，并尝试理解性默写出来完整的代码。这样能直接优化到 1.65s。代码如下：

应用

重要的是卷积形式。这又是什么呢？就是形如 的式子，其中 均不与 相关。显然从卷积的暴力计算方式来看，就不难发现 对应的系数就是要求的 。

于是，只要你能化出卷积形式，就可以用 FFT/NTT 做掉了。典型例题有第二STL行。EG：

所以就能得出核心代码如下：

prufer序列

这个也是相当的重要的。Prufer 序列可以实现无根树和值域为 的长度为 的整数序列之间的转化。

那么怎么转化的呢？先看第一种：树转 prufer。

每一次我都选择当前编号最小的叶子节点，将它的父节点的编号存到序列中，然后删掉这个节点，直到只剩下两个节点。

显然，用堆可以 做。但是如果你仔细想一下就会发现，每删一个点最多再加上一个点。因此我可以顺序枚举点，如果能删就一直删，直到非叶子节点或者编号比初始位置大。时复 。

再看第二种：prufer 转树。

首先由于 prufer 序列的一个非常显然的性质：每个节点在序列中出现的次数就是其度数减一。所以我们每一次选择编号最小的度数为 的节点与当前枚举到的 prufer 序列中的点连接起来，将二者的“剩余度数”减一。当 prufer 序列枚举完后就剩下了两个点，连起来就行。

但是由于和树转 prufer 类似的构造方式，显然仍然可以用类似的方式来线性构造。

有什么用呢？首先他明显证明了 Cayley 定理： 个节点的带标号的形态不同的无根树有 个。

其次，按照 LZJ 所说，会有一些题要用这个序列和一些数据结构搓一下，但是似乎到现在为止他也没有给出相关例题，就先放着吧。

可并堆

斜堆

斜堆应该是非常好实现的一种可并堆。假设我们有 个堆，每一个堆初始大小都是 的。

斜堆每次合并时先比较一下两个正在合并的堆的堆顶，视情况选取更小的那个堆，并将那个堆的左儿子/右儿子和另一个堆接着合并。随后直接交换左右儿子。非常潦草，但是操作均摊下来就是 的。感性证明不难，不会严格证明，想了解的看这里。模板二代码如下：

随机堆

更潦草了，直接在合并的时候随机向左子树或者右子树合并，期望树高是 的，对吧？

左偏树

这个稍微科学一点。我们定义一个节点的 为其到子树中最近的外节点所经过的边的数量。空节点的 。我们让这棵树保持左偏，即每个节点左儿子的 都 右儿子的 。因此左偏树每个结点的 都等于右儿子的 。

所以一种常见的写法是将要合并的和右儿子合并，并且判断满不满足左偏性质，不满足就交换一下。复杂度证明参见这里。

需要提醒一点，上面三种树理论上讲深度可能达到 ，找一个点所在的堆顶要用并查集维护，不能直接暴力跳父亲。

线性建堆

这个会在图论的最小树形图中遇到，所以还是要讲一下。

其实很常见的写法是将要用到的数全部放到一个数组里，然后类似线段树建树的方式给他递归下去建树。

不过我们还有另一种略短一点的写法。我们将所有的值全部建出节点来，放到一个队列里面，然后不停的合并队列的前两个元素，直到只剩一个元素。

虽然还是很潦草，但是理想状态下队首的大小是 。懂吧？如果不完全是 形的数差的也不会太大。

kd-tree

K-D Tree 是一种可以高效处理 维空间信息的数据结构。

先讲建树：

k-D Tree 具有二叉搜索树的形态，二叉搜索树上的每个结点都对应 维空间内的一个点。其每个子树中的点都在一个 维的超长方体内，这个超长方体内的所有点也都在这个子树中。若当前超正方体只有一个点，就返回这个点，否则的话轮流选一个维度，并将这个维度的中位数作为这一维的分割标准。按照这一维的大小分成左右两部分。Eg.:

轮流选择多个维度可以使得树高降到 。正确性显然。查询复杂度是 的。可见效果拔群（雾）。

那如果我们要修改呢？一种常见但是时间复杂度错误的写法是替罪羊树，这样会使得树高降到 级别。而查询复杂度是建立在树高为 的基础上的。

有一种复杂度正确而且相对好写的方法叫做二进制分组。具体的，我们将这些树分成大小为 的许多棵树，查询的时候每棵树查询一次，然后合并结果。如果某一层的大小超了就不停向上合并。均摊 。可以证明查询复杂度仍然是 的。

模板题参考代码如下：

不得不说真的非常屎山，考试的时候最好不要遇到。

颜色段均摊

这个板块的 OI-wiki 写的就是一坨，实用性讲的太少，太简略了。我们还是直接上强度，例题链接。

我们可能需要几个弱化版来逐步拆解这道题。首先是这道题的不带修版本。但是你的做法必须尽可能地支持单点修改。

这到题中，我们可以使用一个数组 ，表示满足 且 的最大的 。如果不存在，则为 。我们注意到，一个数 第一次在区间 出现当且仅当 。因此可以离线下来去做，带修的类似，就是一个带不带修的 CDQ。

我们考虑区间推平呢？注意到，如果原有的一段区间 ，其中 是要推平的区间，那么 的 其实是没有变化的。会变化的只有 ，以及更靠后的第一个同色的位置。其余的情况我们可以通过分裂区间的方式近似的看待。

换言之，将一个原有的区间推平，会影响到的 其实只有 个。

我们注意到，一次完整的推平操作最劣的情况下会推平中间的区间，并将两个端点所在的区间分裂成两部分。也就是说，单次推平操作只会增加 个区间。最开始的时候粗劣的视为 个区间，最后也只会带来 次区间推平操作，对应 次 的修改。

我们考虑一下怎么维护每一个颜色段。我们考虑将所有的区间视为一个包含 的结构体，然后丢到 set 里面，按照 排序就行。这时候，从 节点分裂区间（即对于已有的区间 ，在 set 中将其分裂为 和 两个区间），插入删除区间都是可以简单维护的。如不明白可以去看 oi-wiki。

至此，此题可解。上述思路对应的代码如下：

上述内容是颜色段均摊的第一种表现形式，即区间增减量是线性的，从而可以做到均摊 或者类似的低时间复杂度。

颜色段均摊的第二种表现形式是对于一些操作，随机情况下区间个数是期望为 的。这里不再过多赘述，可以参考 ODT 的起源题。

数学

质数的判定

暴力

对于一个合数 ，他一定会有一个 以下的因数，由唯一分解定理，正确性显然。所以我们检验 到 是不是 的因数就完了。不给代码了。

埃氏筛

一个质数除自己以外的其他倍数一定是合数。所以我们从 开始枚举，如果这个数没有标记就把他的其他倍数全部标记了。复杂度是 的。代码如下：

欧拉筛

又名线性筛，真的是线性的。埃氏筛的复杂度不是严格线性，问题就在于同一个合数会所有的质数给标记。线性筛可以做到只被最小的质数标记。

我们思考对于每一个合数 。那么他其实只有可能被 给标记到。这正是埃氏筛。但是因为有 i % p[j] == 0 -> break，所以说当 的时候其标记到尝试会被更靠前的质数给禁用掉。所以只有在 的时候才会被标记。从而是线性的。

代码如下：

Miller–Rabin

如果 为素数，则 ，设 为奇数，则以下两个命题至少有一个成立：

这个定理的逆定理并不成立，但是如果你取的 足够好，并且多测几组，那么总能将复杂度降下来。事实上如果你取 ，那么它在 long long 范围内的正确率是 。

代码如下：

更相减损法

更相减损法是中国古人发明的一种用来慢速求解 的方法。核心的式子就是 。慢就慢在减法，和下文的欧几里得法一比简直慢的离谱，但是他有它的用处。

我们思考对于两个高精度数怎么快速的求出它们的 gcd。大数的质因数分解是一个世界性的难题，因此一般也就只有从欧几里得法或者更相减损法下手。欧几里得法中要用到高精度取模，非常的慢，而且不好写，因此 OI 中一般采用加强版的更相减损法。具体如下：

显然时间复杂度是和 强相关的了。不过一般见不到。

欧几里得法

间的也很多，用的更是最多的一种算法了，核心式子是 。正确性显然，时间复杂度比 更优，可以理解为是反斐波那契函数的。不过没什么有意思的扩展。

裴蜀定理

定理很简单： 必定存在整数解。扩展欧拉定理就是用来求解不定方程 的，并且其求解过程正好证明了裴蜀定理，因此这里不再赘述，直接看下一节。

扩展欧几里得法

扩展欧几里得法是一种用来求解不定方程 的一种方法。具体流程如下：

首先我们考虑求出来 的一组解，然后将其扩展到 。

现在假设 有解，那么因为 ，所以方程 必定也是有解的。

我们知道 ，因此 。

从而我们得到一组可行的解为 。

然而我们并不知道 的值，不过我们发现这和前面的那个方程形式是完全一样的，因此我们递归求解。

在递归边界上，，此时显然有一组特解为 。

递归完成后我们就能够得到 的一组解了。而显然这个过程是有穷的，因此证明了 必定存在整数解。

接下来， 就是原方程的一组解了。而且显然，由于最大公因数的性质， 不为整数时恒没有整数解。

挺好理解的，代码也不长，只要能够记住将欧几里得法里面的换项同时应用到等式左右两边就做完了。

欧拉定理

。证明:

构造一个集合 ，其中的元素为小于等于 且和 互质的数组成的集合。显然其中有 个。这个 也被称为简化剩余系。

这时候我们在构造一个集合 ，其中的元素为 中的所有元素乘上 。

如果 A 中有两个元素 ，使得 ，则 B 中元素的个数小于 。然而，因为 ，所以 ，矛盾了。所以 B 中的元素仍然为 个。又因为 ，所以

又因为 ，所以 。

拓展欧拉定理

证明的话，感性理解可知，任意一个数的次方模一个固定的数的值最终一定是循环的，而且循环长度可为 ，再加上一个 保证他进入了最终的循环就行。严格证明去扒拉 OI-wiki。

中国剩余定理

中国剩余定理可以求解一类同余方程组：。同时要求 两两互质。

中国剩余定理的核心思路就是构造一组可行解。怎么构造呢？如下：

首先我们令 ，并且令 。

此时有一组可行的 为 。其中 是模 意义下的逆元。

显然吧，代入到每一个方程里面，发现是正确的。

扩展中国剩余定理

其实和中国剩余定理毫不相干，核心思路都完全变了。

扩展中国剩余定理的核心思路变成了合并方程，也就是将两个同余方程合并成一个。这样按照顺序合并完就得到了一个解，或者在中间发现无解。

怎么合并呢？我们假设两个同余方程是 。

显然我们知道 ，也就是 。显然我们可以通过 exgcd 求出来 的一组解，无解就是无解，无限解就是二者等价不用处理。

推出来了一组解之后，我们可以得到 的通解的公式。此时我们将这个公式带回到原先的 就得到了新的一组同余方程。

其实思路还是很简单的。代码如下：

卢卡斯定理

用来快速求解 的方法，其中 较小，一般在 及以下，但是一定是质数，而 可以很大。核心公式：。

设 ，则有 使得 ，再考虑一个二项式：。

先由费马小定理推个结论：。

把这个结论带进去：，再由二项式定理把右边展开 。

同样我们可以把左边展开：。

然后我们可以发现，左右两遍都有 次项（当然，这是在 的情形下，如果 结果就是 ，不用考虑了）。

比较一下它们的系数，左边是 ，右边是 。

这边要说明一下，不会出现别的次数组合，比如 和 ，因为 ，所以：。

即：，证毕。

扩展卢卡斯定理

学扩展卢卡斯定理不需要会卢卡斯定理，就像学扩展中国剩余定理不需要会中国剩余定理。

扩展卢卡斯定理不再要求 是质数。但是不是质数就会少非常多的性质，因此我们想办法和质数扯上一点关系。

我们考虑将 质因数分解，假设 。如果我们能够计算出每一个 ，就可以使用 crt 快速的合并结果，得到答案。

。其中 表示 中 这个质因数的次方数，，也就是将 中所有的质因数 全部去除掉。

是很容易求的，我们现在需要着重考虑 。因为 不是质数，所以请不要像各种神奇的技巧，直接计算答案。

我们模仿 的计算方式，逐步删去多余的 并计算答案。具体的，我们直接扔掉当前区间内 的倍数，并放到下一批继续处理。

假如说 ，那么我们的计算会像这样：

。

。

我们会首先将倍数全部拎出来，抛去一层 之后就又变成了 开头的连续区间，递归处理即可。我们主要考虑剩下的部分。

剩下的部分我们发现仍然是呈现出很强的周期性。单组内的乘积为 。这样的东西我们总共有 组。剩余的部分直接暴力处理就行。

也就是说只要你的模数 满足 不大，就可以快速的计算出你想要的结果。

卡特兰数

卡特兰数非常常见，可应用于以下问题：

  1. 有 个人排成一行进入剧院，入场费 元。其中 人只有一张 元的钞票， 人只有一张 元的钞票。请问有多少种方案使得剧院总有 元钞票来找零。
  2. 有一个大小为 的方格图。左下角为 ，右上角为 ，每次只能向左或向上走且必须满足所有经过的位置 满足 。
  3. 在圆上选择 个点，将这些点成对连接起来使得所得到的 条线段不相交的方法数。
  4. 对角线不相交的情况下，将一个凸多边形区域分成三角形区域的方法数。
  5. 一个栈中顺序放入 的不同的合法出栈顺序数。
  6. 个节点可以构造多少个不同的二叉树。
  7. 个 与 个 排列成数列 ，求满足 的 的个数。

不难发现， 是完全等价的， 是完全等价的。实际上， 的递推式是完全一样的。我们可以得出若干不同的式子：

。

。

一般可以认为边界条件为 。

为什么是这样的呢？先看第二个式子。显然， 就是不考虑 的从 到 的方案数，而 就是不考虑 的从 到 的方案数。这俩有什么联系吗？

我们想一下，如果一个路径不合法，那么他一定会在某一步走到 。这时候，我们将他在 到 的路径反转一下，就像这个样子：

神奇的事情发生了：一个到 的不合法路径被映射到了一个到 的路径。随后，不难证明，每一个不合法路径都会唯一对应一个到 的路径。那每一个到 的路径都唯一对应一个到 的不合法路径吗？

是的。我们直接让他在第一次越过 线的时候就翻折，显然一一对应。证毕，解决 。

第二个式子显然能够推到第一个式子，不用多说了。也可以证明出来第三个式子。那第四个呢？

从 或 都能够推出这个式子。 从分治的角度去想， 从树形 DP 的角度去想都能得到这个式子。证毕，解决 。

那怎么证明这两个式子是恒相等的呢？数学归纳法是一个比较容易想到的方法。读者自证不难？

典型例题：卡常难数。

裸题123456。

应用12。

拓展12。

威尔逊定理

( 为质数)。可以用逆元两两配对证。

一般情况下不考，要考则考的足够板。主要的作用可能就是优化对这类数的快速幂操作的一个 ，或者这道题的用途。主要是第二个。

错排列

简述思路：枚举每个数位置合不合法， 容斥，进一步发现数量相同贡献相同，压缩贡献计算得到 ，进一步化简为 。

记个结论就完了，这东西不太能考的不板。

圆排列

，主要是记住他的最后除掉多统计部分的思想，解决其他类似问题。

多重集排列组合

以下按照这样的方式记录一个多重集 。 中共有 种不同元素 ，其中第 种有 个。该集大小为 。

用到最后除掉多统计部分的思想。全排列大小为 。

如果是普通的排列组合，则需要用到容斥的思想，如下：

对于其组合，先考虑这么一个问题：有 个篮子，把 个元素扔进去的方案数。这种问题常见的处理方法就是隔板法。显然答案就是 。

接下来，我们考虑对于一般的情况。一般的情况其实和上面的问题的本质区别就在于上面的相当于每种元素无限取，而实际上每种元素是有限制的。最多就是其个数。

那么我们其实真的很容易就可以想到容斥。枚举每一种元素超没有，如果第 种元素超了就预先分配 个给他，然后奇偶加减类容斥就完了。一般的排列也有类似的方法，这里不做赘述。

bsgs与exbsgs

BSGS(大步小步) 可以在 的时间内求解出 的最小解，满足 是质数。思路如下：

因此我们枚举 ，将 最后一次出现的位置的 存到 对应的位置（一般用 unordered_map），直接覆盖原有数据就行。

接下来，我们顺序枚举 ，一旦发现在 unordered_map 中存在 ，就直接返回 。如果 枚举完了还没有返回就只能是无解了。

不难注意到 ，无法枚举到 ，因此需要特判这种情况。

在 较小的情况下 越大 越小。正确性比较显然，时间复杂度也必然正确。

哈哈，数论题的拓展最喜欢的就是去除各种互质/是质数一类的限制了！他也跑不掉。思路如下：

于是问题被转化为普通的 BSGS。注意上面 不一定是质数，因此 的逆元要使用 EXGCD 求解。

生成函数

一些前置概念，在后面多个板块会用到。

积性函数：满足 。

那么，知道因式分解时有：

。

常见积性函数：

： 时为 的因子数，。

：莫比乌斯函数。

：欧拉函数。

： 的约数个数。

：。

。（常见写为 ）。

。（常见写为 ）。

普通生成函数

对于数列 ，其 OGF 为 。

看起来不知道有什么用，给个例题：有三种物品，每种物品分别有 个，问从这三种物品里面拿出 个的方案数有多少种？

假设 ：转移到物品 ，已经选了 个。

能不能更方便一些？

对每一个数生成出其生成函数()，即 ，。令 ，则答案为 ，即 的系数。

其实生成函数的系数之间的乘法对应了你手数时每一项选择的过程。

需要注意的是，这些生成函数往往可能会涉及到无穷的累加。请别忘了我们还有展开式，无穷序列加起来可能会变成之前的分式。

典型手算例题有《干饭》和《末日时在干什么》。（不正经.jbg）

其实我们不难看出，绝大多数的情况下， 数组都只会涉及到 两种值，来表示可不可取。拆解的时候多使用换元法，因式分解法，往往会有奇效。

补充一个公式：。

指数生成函数

对于数列 ，其 EGF 为 。

对于大部分带标号的问题，可能会有类似的形式：。一个典型的例子就是多重集的排列。

有 ，即 。

因此这么定义。这里较为常用的公式是关于 的泰勒展开。

有一个公式需要记一下：

。证明显然，展开后就是了。

一个典型的应用就是求可重集的排列数。如题，代码如下：

狄利克雷生成函数

对于无穷数列 ，其 DGF 为 。

如果 满足积性，那么其 DGF 也可以由质数幂处的取值表示为 。

有一些常见的 DGF，可以记一下。

黎曼函数 可用序列定义为 ，另一种形式为 。

莫比乌斯函数的 DGF 定义为 。也就是说，。

欧拉函数的 DGF 定义为 。也就是说 。

狄利克雷卷积

若 ，则令 。

积性，则 积性。

若 ，则称 互逆。

可以做到 求 或 。

对于其余的卷积，其复杂度一般为 ，调和级数。

莫比乌斯反演

本质：。

证明：。

其中的 指 的质因子个数。

，。

则有 ，。显然，函数的逆放到这里一定成立。

主要应用就是拆 。套路就是去枚举 的值，然后对取等条件作卷积。

最常用的场景就是 ，尤其是 的形式。

一种较为常见的形式是求 。这时候我们构造函数 ，满足 。原式转化为 。

典型例题就是这道题。

亚线性筛法

杜教筛

杜教筛是个神奇的东西，对于 ，满足 的函数，也就是积性函数，它可以在 的时间复杂度内求出 。通过合适的预处理可以降到 。

具体的，对于一个积性函数 的话，我们可以知道对于任意数论函数 有 。其中 表示的是迪利克雷卷积。

于是，我们可以使用记忆化与整除分块来做上述操作。时间复杂度证明略。注意当且仅当处理到了 的时候才有 的求解复杂度。递归求解即可。

模板题在这里。

PN筛

min_25筛

https://www.luogu.com.cn/article/m8uwkv2f

第一类斯特林数

第一类斯特林数有通用标记：。他表示的组合意义是将 个人分配到 个非空环上的本质不同的方案数。其中环不作标号区分，人做区分。

那么它怎么求呢？显然我们可以整出来一些递推式。我们怎么从 推到 呢？也就是多了一个人会多产生哪些情况呢？

首先，它可以新开一桌，从 推到 ，系数为 。

其次，他可以加入原有的位置。显然，因为是圆桌， 个人就会有 个本质不同的空隙。因此可以从 推到 ，系数为 。

从而，。边界条件为 。

通过其组合意义，我们可以推知如下式子：

比如有这么一个例题。思路就是将能看到的和被他挡住的视为一个环进行求解。

第二类斯特林数

第二类斯特林数也有通用标记：。他表示的组合意义是将 个人分配到 个非空无序集上的本质不同的方案数。其中环不作标号区分，人做区分。

那么它怎么求呢？显然我们可以整出来一些递推式。我们怎么从 推到 呢？也就是多了一个人会多产生哪些情况呢？

首先，它可以新开一个集合，从 推到 ，系数为 。

其次，他可以加入原有的位置。显然，本质不同的就是 个集合。因此可以从 推到 ，系数为 。

从而，。边界条件为 。

通过其组合意义，我们可以推知如下式子：

这个例题就行，一眼差不多能出思路，而且不太板。

斯特林反演

按照之前的整理，其本体其实长这样：

若，则 。

若，则 。

不过，这次我们着重讲的是 和 之间的转化。

所以，要下降幂干什么呢？下降幂有如下两种美丽的变化：

。这两个看起来就挺有用的。

所以，怎么变呢？

。

。

可以通过组合意义较容易地证明出下面的那个式子。或者数学归纳法也是可以的。如图：

变换完之后可能可以和前面的一些项合并，换位等，得到一个好处理的式子。

这两天没有自己手推出来的比较好的式子，放一个题解做样例吧，对应这道题。

二项式反演

flag。

若 ，则 。

证明：错排问题。

我们让 表示 个人随便站的方案数， 表示恰好 个人站错的方案数，显然满足了第一个式子，而对于第二个式子而言也是适用的。

二项式反演可以实现“至多”/“至少”和恰好之间的转化。

同理也有：若 ，则 。

上述的两个式子是比较常用的两个。从本质思想来讲呢，这两个式子都是类似于容斥的形式推出来的。

也就是说，如果我能够构造出来一对合理的 ，那他一定对应着一种组合意义下的容斥方式。

所以，二项式反演提供了一种更加快速的找容斥关系的方式，而容斥因其逻辑更加底层，反而能解决更多的题。

当然这么说有点绝对。既然是一个反演，那他一般有超出其根源的用途。在解决一些计数问题的过程中，二项式反演公式对简化问题有着重要的作用。只是例题目前不太有体现。

burnside定理

Burnside定理：。其中 是所有置换所构成的集合， 是置换 对应的本质不同的集合的个数。

怎么理解呢？例题：有 种颜色的珠子，你要用他们来构成一个有 个珠子的手环，问有多少种本质不同的手环。这里本质不同定义为旋转或翻转后二者仍不同。

那么，其置换包括旋转 度，沿对角线/对边线翻转，共 种。 是指的置换 对应的本质不同的集合的个数。也就是求经过置换 后仍一样的方案数。

例如：

对角线上的分别属于两组，因此总共有 种本质不同的手环。

总共有三组，因此共有 种本质不同的手环。

因此，最终的答案为 种。分子上的每一项依次对应转 度，两种沿着对边翻，两种沿着对角翻。

往往需要静下心来推一下 ，给一道例题。

polya定理

Polya 定理可以视为是 Burnside定理在较简单的问题上的特例化。其式子如下：

。

肉眼可见的，这里我们认为 。而如果我告诉你 表示的是置换 的循环节数，这里的循环节是指的有向移动形成的环，那么这个公式的意义就更加明了，甚至不证自白了。

另给一道例题。

博弈论

博弈论主要研究具有竞争或对抗性质的对象，在一定规则下产生的各种行为。博弈论考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略。

通俗地讲，博弈论主要研究的是：在一个游戏中，进行游戏的多位玩家的策略。

在 OI 中，我们也有时会遇到这些题。其中最常遇到的是公平组合游戏。参考这篇博客。

首先，在 OI 当中，我们常研究的是平等博弈，也就是说，可允许的操作只和当前局面的状态而和操作的玩家无关。

公平组合游戏

若一个游戏满足：

  1. 有两名玩家交替行动；
  2. 在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关； 3.不能行动的玩家判负。

则称该游戏为一个公平组合游戏。

这时候有一些比较重要的概念：有向图游戏，必胜态和必败态。

给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿着有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。

那么不难发现，任何一个公平组合游戏都可以转化为有向图游戏。游戏状态为点，状态转移为边。

必胜态：存在一种策略，可以让剩余的状态变成必败态留给对手的局面。

必败态：不管采取什么策略，这一步行动后对手都处于必胜态的局面。

简化一下，就是三个定理，这也是博弈论的核心：

这里举出若干公平组合游戏的例子。

Nim 游戏：

地上有 堆石子，其中第 堆有 颗石子。每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。问是否有先手必胜策略。

这时候，我们似乎无从下手，那让我们从有向图游戏的角度去下手，考虑图上的必胜态，必败态。

首先，有一个必败态是剩余石子全为 。不难发现他们全部异或起来为 。

随后我们发现了一个不得了的可能正确的结论：当且仅当 时先手必败。

先证一个引理：当 时，必定存在方案，将其中一个数变小之后满足 。

因为异或是二进制下的不进位加法，也就意味着异或值的最高位一定有至少一个数是 。这时候我们取其中任意一个数异或上现在这个值，他的值一定变小了，而且现在异或起来的值显然为 。

首先，充分性很容易证明。当先手拿掉一些石子，使其异或值变化时，我们一定存在一些方案使得其异或值变为 ，也就是我们的引理。

必要性呢？当 的时候我们可以构造使得 。而 是必败态，从而 是必胜态，也就是说必败态只可能 。

证毕。题目。

台阶 Nim 游戏：

有 级台阶，第 级上有 颗石子。每人每次可从任意一堆石子里取出任意多枚石子放到下一级台阶上，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。问是否有先手必胜策略。

首先，我们可以认为偶数级台阶上的是无效的。因为先手将若干颗移动到下一及后，后手可以再将这些石子移动到下一级从而将这堆石子再次移动到偶数级，最终移到 。

于是我们发现，将石子从奇数阶移动到偶数阶就是丢弃，将石子从偶数阶移动到奇数阶如果不能使奇数阶上的石子数异或值为 就是白给。

而我们只通过将石子移下奇数阶就可以做到使奇数阶上的石子数异或值为 。

从而得出结论： 时先手必胜。

证毕。题目。

Moore's Nimk：

两个人玩取石子游戏，共有 堆石子，每个人每次可以从不超过 堆石子里面取任意多个石子（不能不取），不能取的人输。问先手必胜条件。

给出结论了就可以用类似于上面的方法整出来了：将每一个数写成二进制形式，则如果每一位上 的个数都是 的倍数，则先手必败，否则先手必胜。

这个有前面的铺垫，读者自证不难？就不赘述了。

还有两个可能见到的，记一下结论就行了，因为证明有点怪怪的，有点脱离了我们之前所构建的体系，所以不详讲。

Wythoff 博弈：

有两堆石子，石子数可以不同。两人轮流取石子，每次可以在一堆中取，或者从两堆中取走相同个数的石子，数量不限，取走最后一个石头的人获胜。判定先手是否必胜。

先手必败当且仅当 ，非严格判等，整数部分一样即可。

证明。例题-1，例题-2。

Fibonacci 博弈：

一堆个数为 的石子，有两条规则：

  1. 先手不能在第一次把所有的石子取完，至少取 颗
  2. 之后每次可以取的石子数至少为 ，至多为对手刚取的石子数的倍。

约定取走最后一个石子的人是赢家，求先手必胜态。

先手必败当且仅当石子数为斐波那契数。题目。

SG 函数

这个也是相当的重要的。

首先有一个函数 。

假如说状态 有 个后继状态 ，那么 。

由于一般情况下没有后继状态的可以视为必败态，因此 必败，反之必胜。因为 与必败必胜态极好的对应关系，其正确性不证自明。

最直接的应用就是 Bash 博弈和其拓展：集合型 Nim 游戏。

Bash 博弈：

总共有 个石子，每次每人可以取 个石子，问先手必胜状态。

先手必败当且仅当 。非常裸的 SG 函数，。递推可证。题目。

集合型 Nim 游戏：

给定 个整数组成的集合 , 给定 堆石子的数量 , 两位玩家轮流操作，每次操作可以从任意一堆石子中拿取石子，每次拿取的石子数量必须是集合 中的整数，最后无法操作的人失败。判定先手是否必胜。

直接暴力推 SG 函数值就行了。题目。

移棋子游戏：

给定一个有 个节点的有向无环图，图中某个节点上有棋子，两名玩家交替移动棋子。对于给定的图和棋子初始位置，双方都会采取最优的行动，询问先手必胜还是先手必败。

这样的话仍旧是非常裸的 SG，那我问你，如果图上有多个棋子呢？

答案很眼熟：当且仅当每个棋子的 SG 值异或起来为 时先手必败证明：

不难发现这个问题和丢石子的那个问题是很像的。当你在某个非零状态下时你可以丢掉任意颗。虽然即使你一颗都不剩，你也可能可以做到增加，毕竟求的是 ，但是这也意味着对手恒存在一些方法能给你变回来。当你不存在增加的变换的时候你的旅途也就到此为止了，只能老老实实地减。

而又因为你在某个非零状态下时你可以丢掉任意颗，所以你总能维护异或值为 。

证毕。题目。

相关的有许多变种，比如 Anti-SG，Multi-SG，Every-SG，可以自行参阅开头的博客。

随便给几道例题：1，2，3。

二次剩余

求解同余方程 。你可以假定 有解且 为奇素数。

若方程 有整数解，则称 为模 的二次剩余，否则称 为模 的二次非剩余。

先给出结论：寻找一个整数 满足 为模 的非二次剩余，并定义 。答案就是 。

额，后面会证明出来 没有“虚部”。

二次剩余判定定理

是 为模 的二次剩余的充要条件。

必要性显然，充分性：

令 ，其中 为模 意义下的原根。

将 带入，得 ，所以 ，所以 ，即 是偶数。

所以， 为原方程的解，即 为模 的二次剩余。证毕。

同时我们也可以发现，因为 ，所以 ，也就是说， 是 为模 的二次非剩余的充要条件。

他至多有 个不同的解

假定 是其中任意两个解，则 ，则 。因此 或者 。因此最多只有两个不同的解。

以上两个定理保证了可解性。

接下来，我们推 ，看看是什么东西。

又因为存在性定理，显然当存在解时会分别得出两个根，或者干脆就是 。因此 没有“虚部”。

你问我怎么找合适的 的话，其实不难发现二次剩余和二次非剩余正好一半一半，随机化的话期望 次就能找到。相信自己的运气不会差到抽中 。

线性基

线性基，其概念可以视为向量的基底。

也就是说，假设给定元素集 ，你可以构造出来另一个集合 ，使得 中所有元素都可以用 中的元素表示，而 中任意一个元素都没法只使用 的其他元素表示出来。

不管怎么说，由于任何意义下的向量的美妙的性质，我们一定要保证 中的每一个元素的第一个非零位置不重。

而这个东西在信息中，应该能感觉到是生来就有用的。毕竟他给出了一大坨信息的一种高效压缩方式。

事实上的确如此。在信息中，我们更多研究的是异或线性基。也就是说，我们只用 中元素进行异或操作。

这个博客就挺好。另外，由于贪心能支持的面超过了高斯消元，且可以在 的复杂度内转化，所以不整理高斯消元。

异或线性基

贪心怎么贪呢？首先从高位向低位扫，当这个数这一位是一时，如果线性基中没有元素最高位是当前位，那就把它放到线性基中，否则把他异或上线性基中的那个元素，继续进行。

接下来，我们可以应用一下，比如我们现在要求出来一堆数的最大异或值。

显然，我们从大到小去枚举，如果当前这一位为 并且这一位有线性基，那就异或一下，否则不动。代码如下：

但是这样还没完。如果很不巧他让你求 小异或值，那你线性基不就炸了吗？

不好意思，没炸。仔细想一下，会导致大量策略出问题的地方就在于判断这一位为 并且这一位有线性基。如果这一位有线性基就可以毫无顾虑地异或是不是就很简单了？

欸？如果我们强制保证是最高位的那些位仅在那一位的线性基上是 不就做完了？

所以我们只需要对每个最高位的线性基进行检查，具体的如果比它更小的线性基在这一位有值就异或上他。从小到大进行检查即可。

或者，你用小线性基去消大线性基也是一个道理。当然这还没有结束，我们还需要求 小异或值。

解除了刚才的制约，我们真的不难想到，当你选择了更大的线性基的时候，小的线性基也无力回天。

大的严格压制小的，且不影响小的，那就和线段树上二分等等的没区别了。更加明显的，每一次选与不选恰是 的二进制位！

唯一需要注意的就是有没有 了。代码如下：

前缀线性基

这就很有生活了。他可以求解出一个数组在区间内的最大异或值！

怎么做到的呢？一句话：我只要最新版本。在下标 时，先将 位置的线性基拷贝过来，然后尝试加上 位置的数。如果遇到空位就直接填进去。

如果这一位是 且此位有线性基，那就比较二者的最后更新时间（初始状态下当前持有值的最后更新时间为 ），如果持有值更新，就顶替原有值，并将手上拿的改为原有值。

做完了操作之后再异或一下手上的值（和线性基值），直到手上的值为 或者填上坑了。

代码如下：

求 的时候，第 位的线性基有效当且仅当这一位的最后更新时间在 及以后。

数论线性基

这个名称可能不严谨，但是确实能让我们知道他和异或线性基的区别。数论线性基可以理解为一堆向量的大小最小的基底。

这甚至更简单。就是拿着贪心的思路暴力模拟就完事了。

行列式

行列式，按照我目前的理解，就是对一个 的矩阵的一种计算（或者更本质的，就是对指定顺序的 个数的一种特定的计算方式，不过比较有用，像矩阵乘法一样）。

行列式的计算公式/定义式：。

其中的 分别表示长度为 的全排列集合，一个全排列，以及这个全排列的逆序对的奇偶性函数，奇数个就返回 ，否则返回 。

直接按照定义进行计算的时间复杂度至少是阶乘级别的，用处不大，所以我们考虑优化其求值。

性质/高斯消元优化

一种常用的高效的方法是使用高斯消元，但是其定义式一脸不可消样。我们需要挖掘一些有用的性质才能够使用高斯消元。

我们考虑证明。假设我们原先有一种方案，这两行取的位置分别为 。行交换，那么我们同样也换一下他们在 中的位置，保持 完全不变。此时可能变号的就只剩下 了。

我们浅浅的分析一下。交换 之后，产生影响的是除了他们所在的那两行的其他行，以及他们本身带来的 。

不是一般性的，我们假设 。事实上 产生的对于逆序对的影响就是 的相反数。

除去这些数之后剩下的就是在原先的两行之间的大小介于 之间的。这些数会产生 个新的逆序对。

因此逆序对的奇偶性必定发生变化。得证。

显然成立吧？在原先的几乎所有运算都不变的情况下在这一行对应的 那里乘了一个 ，提出来公因式就得到 。

这个的证明也很简单，直接对着他的定义式提一下公因式就完了。

这个的证明比较巧妙。我们注意到交换任意两行，行列式变号。因此，我们交换相同的两行，行列式变号。但是又因为这两行相同，所以说行列式的值不发生变化。能同时满足变号且数值不变的只有 。

我们需要用到上面三个性质。首先利用第三个性质分裂出两个行列式，然后用第二个性质分离出其倍数，最后用第一个性质证明这个部分的贡献是 ，得证。

到此，我们发现行列式几乎具有高斯消元所需要的所有性质，直接做已经没有问题了。所以我们再来一个小小的加速：

也就是说我们只需要把整个矩阵给消成到阶梯状的就可以结束了。

应用

应用真的很单一了，几乎就只有一个矩阵树定理。

字符串

字符串哈希

为什么这个东西放在了最前面呢？道理很简单。这个东西很简单，但是能替代部分需要用一些略显复杂的算法才能维护的东西。

假定我们现在有一个字符串 ，下标从 到 。那么 位置对应的哈希值 为 。

其中， 为一个选定的至少比 的字符集大的质数（常用 ）， 是对 字符集到数字的唯一对应， 是一个指定的模数。有时用 unsigned long long 的自然溢出，即 ，但是容易被卡，所以 也常用一些大质数（常用 ）。

也有递推的形式，更加常见：。

那么具体怎么用呢？哈希最常用的用处就是判断两个量相不相等。用哈希来比较两个完整串显然大材小用，一般他会用来比较多个字串是否相等。

对于 到 的字串，其哈希值为 。

显然，对于任意的字符串，只要你选取的 映射方式和 数一致，那么对于任意的相同子串的哈希值也是一样的。下证：

看回 的直接计算形式，并带回哈希值计算方法，发现其值为 。我们令这个子串为 ，不难发现，对 整个串做哈希，其值为 。又因为 ，所以 。

也就是说，用一个字符串 去截取子串所得到的哈希值，等于这个子串本身的哈希值。那么任意一个串中去截取同样的一段得到的哈希值也必然是一样的。

于是，恭喜你，得到了一种快速比较两个子串是否一样的方法。其作用不用我说也是相当大的。

kmp

主要是最长 。一般记一个串在 位置的最长 为 。

最长 指以位置 结束且是字符串前缀的子串的最大长度。 表示以位置 开始且是字符串前缀的子串的最大长度。特别约定 。

那 KMP 怎么玩 呢？

暴力求解可以被形如 的串卡到 ，我们需要一些性质来优化。

假设有一个串，我们来求他的 ，并且已经求出了前 位的值。

在考虑 位置的时候，我们不难发现，。这一点可以使用 的性质使用反证法非常方便的证明出来，不作赘述。

但是只是用这一点的话并不能做出什么特别有效的优化，毕竟往回跳的时候会需要 的验证，整体是 的。

再接着思考一下，当 的时候，。当 时，我们则希望找出一个仍满足 的性质，且长度最长的一个前缀兼后缀字串。这至少可以告诉我们，这两个字符串除最后一个字符以外的字符一定一模一样。

仔细想一下，因为现在我们有每一个前缀字串的最长公共前后缀，对于一个最长公共前后缀的最长公共前后缀，他也一定仍然是原前缀子串的公共前后缀。也就是说，在长度尽可能长的情况下， 会是我们第二个考虑的可能的字符串。如果仍然不对，我们就一直考虑 ，直到上述值为 （即不存在符合要求的公共前后缀）或找到一个符合要求的值，使得 。

这样，因为每一次 都至多增大 ，而且后退的次数一定不大于前进次数，因此复杂度为 。

其实说起来复杂做起来简单。核心代码大概就是 行的样子。那这个 有什么用呢？

很简单，字符串匹配。对于一个主串 和一个模式串 ，它可以用 的时间求解出来 在 中出现了多少次。

我们回忆一下暴力匹配的过程：从头匹配，遇到不符合就匹配下一个位置，直到匹配完匹配串。

再思考一下最长 的性质，不难发现，如果这一个位置匹配不上，那么他的最长 位置是最长的仍与前面的字符匹配的前缀子串。也就是说，我们没必要从头开始匹配，而是变相的从这个位置继续，改变已匹配的位置之后接着匹配。

这样做显然不会漏解，要是漏了，就与最长 的性质相违背。

对于【模板】KMP 而言，他就是问你 的 函数值和 在 出现的位置。可解。

kmp自动机

KMP 自动机，就是在 KMP 的基础之上增加了更为全面的失配指示信息，使其成为了一个真正意义上的自动机。

具体来说，当我们使用 KMP 匹配时发现失配的时候，我们会不断的跳转 直到重新匹配上。然而在更复杂的环境下（比如正则匹配等），这种匹配方式不够灵活、高效。因此我们直接对于每一个位置，记录出他对于每一种字符失配后的跳转位置。

那么这个预处理的时间复杂度是多少呢？不会是对于每一个位置枚举后暴力跳转吧？

事实上，我们注意到，因为我们是不停的在跳转 ，比较是否正确，正确就指向 ，不正确就继续找 的 ，以此类推。

那也就是说， 的答案对于自己同样适用！唯一的区别就是当前的字符匹配上了，那么这个位置更新一下。换言之，我们记录失配数组为 ，那么我们先置 ，然后特殊处理 。这显然是 的。

我不知道有没有人闲的没事去卡 的时间复杂度，这时候你可以使用可持久化数组做到预处理为 。不过显得很愚蠢，因为 KMP 自动机生来就是为了提高大量文本匹配的效率的。

不过一个更加典的应用就是匹配型计数问题，常见的形式就是问(不)含有某个子串的串计数。

不难想到失配本质上就是跳转对应字符的失配指针，从而快速的计算，得到 DP 的转移式。一个非常板的例题。题意就是问你长度为 的不含一个长度为 的模式串的串的个树对 取模。

首先容易设计出一个非常常见的 DP 式子：，表示匹配到答案的第 个字符，模式串的第 个字符的方案数。

不难注意到，类似于 KMP 匹配的的方式，转移到 时确实只和 层相关，转移式为 。其中 表示模式串匹配到 位置之后加一个字符匹配到 的方案数。

这个东西可以暴力 ，可以朴素 KMP ，也可以 KMP 自动机做到 。显然我们现在会第三种，而且几乎不用动！

最后给转移套一个矩阵快速幂就完了。这里有另一道略微困难一点的典题。

失配树

这里的失配树指的是 KMP 的 border 连接形成的树。其本质上是单模式串在 ACAM 中的失配树。故称。

失配树应用较为广泛，这里举几个例题介绍一些典型应用：

  1. 字符串匹配

这就不用多说了吧，就是对应的 KMP 匹配字符串的过程。但是要想清楚这一个应用的原理。他是后面多数应用的理论基石。

  1. 求出某个串的所有 Border

一个十分显然的结论是 。考虑位置的包含关系易证。

也就是说，。这正好和失配树的结构有着紧密的联系。

比如说这道题，可以转化为求所有前缀的 。显然就是最接近树根的祖先，可以 求解。当然也存在直接修改 的更为简单的做法：既然每一个位置都要求 ，那我就先求 ，然后暴改 。实现方式就是暴力跳，跳到最底下了就把 的 偷换成 。不难发现这个过程很像在 fail 树上进行 次带记忆化暴力跳树。所以时间复杂度是 的。

又比如这道题，题意为求所有前缀的满足长度不大于原串的一半的 的个数。一种方法是在 fail 树上直接 dfs，然后利用单调性直接套一个栈就可以解决。或者，我们首先在求最长 的时候顺便把每个点在 fail 树上的深度求出来，然后使用类似于求解最长 时记录的那个 ，利用其限制和扩展的双重连续性进行扩展与收缩。时间复杂度 。

  1. 求两个前缀的最长公共 Border

显然，有了前面的铺垫，我们不难想到，也不难证明答案就是他们在 fail 树上面的 LCA。放一道模板题就行了。

  1. 统计每个前缀的出现次数

先给出结论：这个位置在 fail 树上对应的节点的子树大小。这一点也不神奇。

我们注意到，当一个前缀在序列的中间出现的时候，他就是原序列中以他在中间那个串的结尾为结尾的串的 Border。而我们思考跳 fail 树的反祖边就是按长度倒序枚举所有 Border。证毕。

更为强悍的应用可以参见这篇博客。

马拉车

Manacher 是一种可以以线性的时间复杂度标记出一个字符串中所有回文串的位置的算法。

听起来比较神奇，不过不难想到回文串的中心位置只会有 个，并且一定是向外一定距离后不再是回文串。事实上 Manacher 就是处理每一个中心位置的最大回文距离。

我们首先考虑中心位置全部是原字符串的某一字符的情况。记最大回文距离为 ，当前的边界最靠右，同时左边界最靠左的的回文串在 。

考虑转移答案到 ，不妨假设我们已经处理完了 。

如果 ，我们直接从 位置开始暴力扩展其边界，也就是直接枚举找到最大满足要求的 。别急，等会儿分析时间复杂度。

其余的情况下，由于 处在 的大回文串内，所以我们大胆假定 ，其中 与 在 区间内是一个对称的位置，也即 。

然而事实上这并不总是成立：可能 超出了 的范围，可能 ，外面的字符正好满足要求。总之：失去绝对对称性。

一个看起来非常有道理的做法是将 截断至 ，然后暴力扩展，但是时间复杂度没有保证(?)。

其实不然，上述做法就是标准的 Manacher。时间复杂度严格线性。

因为无论是回文串外的暴力扩展，还是回文串内的截断扩展，都指向一个事实： 只增不减。而在大回文串内部不存在枚举并进行扩展的可能性。因此总次数就是 的。

别急，偶数情况还没有处理！

我们发现，在两个相邻字符之间随意插入一个字符集外的特殊字符，就相当于给偶回文串的中间位置强制指定了一个字符，规约到奇数长度回文串。模板题代码：

事实上，Manacher 能处理的远远不只回文串个数统计等板子题，还可以处理一些有限制的回文串计数问题。例如此题。

我们需要理解 manacher 的算法本质：利用回文串对称的特性利用对称位置的信息。

比如说这道题统计的就是一个特殊字符不少于一半的回文串的个数。我们考虑使用 manacher，并且每一个位置不只是记录最长回文串长度，还多记录对应的 ? 的个数，满足要求的权值和等信息。

为什么呢？因为我们知道区间长度如果超了，就需要截断。然而像之前一样直接截断长度就会导致贡献不正确，所以需要额外记录信息来支持回滚。

总之，万变不离其宗，核心思想就是 manacher 的算法本质。我们主要就是想办法维护一些信息，然后支持其中有的操作而已。

这道题的核心代码如下：

exkmp

这个东西为什么和 KMP 分开了呢？因为这个东西和 KMP 几乎没有任何关系！反而，他和 manacher 的表现形式非常相似。我们不难发现，对于非 AM 类型的高效字符串算法，多数情况下都是在利用已经求出来的信息加速当前位置的求解。常常是均摊 。

exkmp 主要是在求解 函数。对于一个字符串 ， 表示 与 的最长公共前缀 的长度。

我们思考一下这个东西怎么求。乍一看，似乎很难利用起来前面求过的 的值。因此我们需要深挖一些性质。

我们思考这样一件事情：如果当前位置 处在 当中意味着什么。如图所示：

不难发现，图中所示的绿色部分是完全一样的。也就是说， 位置可能可以考虑继承 位置的值！

但是这是不是一定对呢？不难想到，如果 ，也就是说 位置开始的 完全在 位置开始的 的内部的话，那显然是正确的。但是如果恰好贴在边界上，甚至超出了边界呢？不难想到因为信息不齐全，所以说只能够先截断到 ，然后暴力扩展。

更进一步，如果不存在这样的 了，我们是不是又只能够暴力扩展了？欸？有点熟悉！

如果我们不停地维护 最靠右的那个区间，是不是右端点的移动就是 次，类似于 可以做到均摊 呢？

对了。这就是 ExKMP。不过有一个细节：如果你把 位置也给加入到循环当中，就会发现 ，也就是尝试利用自己的信息，但是因为没有，所以说退化为 的暴力。所以我们从 位置开始求，最后把 设置为 。

显然 ExKMP 也可以求 的所有后缀与 的 啊！我们令 ，其中 ，也就是一个异于其他字符的分隔符，那么 部分的 函数的值就是答案了。

ac自动机

如果你已经充分理解了 KMPAM 的话，那么这部分内容会变得非常轻松，否则我将需要花费大量时间解释各种概念。我不会这么干的。所以如果你不会，请往上翻。

一句话：AC 自动机就是在 trie 树上实现的多模式串 KMPAM。

做一点简单的解释：因为是多模式串，而且在 trie 树上面，因此每一个节点的 fail 指针都是指向 trie 树上的节点的，而且不一定反祖,是所有模式串中能找到的最长公共前后缀。同理，fail 指针构成了一颗树，也叫失配树。在此基础上维护快速失配转移就形成了 AC 自动机。

参考 KMP 的最长 Border 的构造，我们得到 AC 自动机的 fail 指针构造方式：

令 通过字符 指向当前节点 。若有 指向 的节点，则 为所指向节点，否则继续向上找上一个 fail，即 ，以此类推。如果到了根节点仍然没有则指向根。

下面讲一个重要的统计效率提升，参见模板题。

首先暴力匹配的过程想必大家都是可以自己 YY 出来的，和 KMP 去匹配的唯一区别就是每到一个位置都需要跳 fail 跳到根节点，以便更新当前匹配到的后缀的模式串。显然这部分的优化空间是极大的。

如果一定要考虑在线的话，那么记住 fail 指针构成一棵树。你可以使用重链剖分等技巧在线维护。不过鉴于这是多模式串匹配，这类询问并不常见。我们考虑有没有希望离线做到线性。

记住 fail 指针构成一棵树。你可以在每一个位置标记直接增量是多少。匹配完之后，一个点的实际出现次数就是其子树内的所有节点的直接增量和。

接下来是一个好题，似乎也比较的经典。一定要仔细思考一会儿这道题，不要像我一样浪费了，关键是整理的时候再看发现又忘了。

无论是 KMPAM 还是 ACAM，其中的 fail 的含义大致相仿：都是后缀集合。

这道题的一个简单的第推关系是 。其中 为字典。然而，暴力去匹配这个东西是肯定会超时的（虽然第一个 Subtask 在现在的硬件下容易创过去）。

我们考虑优化匹配过程。容易注意到题目中 的较为小的值。这启示我们使用状压。但是压什么呢？

回顾转移式。有效的 的范围就是 ，而且 是布尔类型的。而显然在 ACAM 中固定匹配位置的所有后缀串的存在性是固定的。也就是说 与对应的 实际上都是可以快速预处理的。弄一个状压，然后按位与判零即可。

后缀自动机

SAM 虽然叫做后缀自动机，但实际上他对于所有子串的优秀的压缩效果及其用途才是我们更为关心的。直观上，字符串的 SAM 可以理解为给定字符串的所有子串的压缩形式。实质上，字符串 的 SAM 是一个接受 的所有后缀的最小 DFA。

首先，SAM 本身包括这么些东西：

  1. 点（状态），其实就是为了便于边的维护。
  2. 边（转移），边带权，带的是字符集中的某种字符。
  3. 终止状态，如果我们从初始状态 出发，最终转移到了一个终止状态，则路径上的所有转移连接起来一定是原串的一个后缀。原串的每个后缀均可用一条从 到某个终止状态的路径构成。

仅仅考虑这些的话，SAM 就是一个 DAG。

SAM 最重要的性质是，它包含关于原串的所有子串的信息。任意从初始状态 开始的路径，如果我们将转移路径上的权写下来，都会形成原串的一个子串。反之每个原串的子串对应从 开始的某条路径。

到达某个状态的路径可能不止一条，因此我们说一个状态对应一些字符串的集合，这个集合的每个元素对应这些路径。

看起来好像确实非常有用，但是问题在于我们怎么用一个高效的方式给他构造出来呢？实际上，我们可以做到线性时空复杂度。我们需要两个非常重要的东西：结束位置(endpos)和后缀链接(link)。

结束位置(endpos)

考虑字符串 的任意非空子串 ，我们记 为在字符串 中 的所有结束位置（假设对字符串中字符的编号从零开始）。例如，对于字符串 ，我们有 。

两个子串 与 的 集合可能相等：。这样所有字符串 的非空子串都可以根据它们的 集合被分为若干等价类。

显然，SAM 中的每个状态对应一个或多个 相同的子串。换句话说，SAM 中的状态数等于所有子串的等价类的个数，再加上初始状态。SAM 的状态个数等价于 相同的一个或多个子串所组成的集合的个数 。

endpos 有若干定理性质， 中写了三条，但其中 条均可由第 条得到：

若 ，则：

正确性显然。

后缀链接(link)

考虑 SAM 中某个不是 的状态 。我们已经知道状态 对应于具有相同 的等价类。我们如果定义 为这些字符串中最长的一个，则所有其它的字符串都是 的后缀。

我们还知道字符串 的前几个后缀（按长度降序考虑）全部包含于这个等价类，且所有其它后缀（至少有一个——空后缀）在其它的等价类中。我们记 为最长的这样的后缀，然后将 的后缀链接连到 上。

换句话说，一个后缀链接 连接到对应于 的最长后缀的另一个 等价类的状态。

与之相关的也有两个性质定理：

所有后缀链接构成一棵根节点为 的树。

通过 集合构造的树（每个子节点的 都包含在父节点的 中）与通过后缀链接 构造的树相同。

这两个性质放一起构成了 SAM 构造中最重要的理论依据。现在我们终于可以讲构造过程了。这个算法是在线算法，我们可以逐个加入字符串中的每个字符，并且在每一步中对应地维护 SAM。任务转化为实现给当前字符串添加一个字符 的过程。一开始 SAM 只包含一个状态 ，编号为 （其它状态的编号为 ）。为了方便，对于状态 我们指定 （ 表示虚拟状态）。算法流程如下：

  1. 令 为添加字符 之前，整个字符串对应的状态（一开始我们设 ，算法的最后一步更新 ）。
  2. 创建一个新的状态 ，并将 赋值为 ，在这时 的值还未知。
  3. 现在我们按以下流程进行（从状态 开始）。如果还没有到字符 的转移，我们就添加一个到状态 的转移，遍历后缀链接。如果在某个点已经存在到字符 的转移，我们就停下来，并将这个状态标记为 。
  4. 如果没有找到这样的状态 ，我们就到达了虚拟状态 ，我们将 赋值为 并退出。
  5. 假设现在我们找到了一个状态 ，其可以通过字符 转移。我们将转移到的状态标记为 。
  6. 现在我们分类讨论两种状态，要么 ，要么不是。
  7. 如果 ，我们只要将 赋值为 q 并退出。
  8. 否则就会有些复杂。需要复制状态 ：我们创建一个新的状态 ，复制 的除了 的值以外的所有信息（后缀链接和转移）。我们将 赋值为 。
  9. 复制之后，我们将后缀链接从 指向 ，也从 指向 。
  10. 最终我们需要使用后缀链接从状态 往回走，只要存在一条通过 到状态 的转移，就将该转移重定向到状态 。
  11. 以上三种情况，在完成这个过程之后，我们将 的值更新为状态 。

算法本体讲解完毕，模板题代码：

看看这个：yutong.site/sam/。

那他的应用呢？挺多的，列例题讲解吧。

T0,【模板】后缀自动机（SAM）,省选，板子题。

T1-1,SUBLEX,省选&&T1-2,[TJOI2015] 弦论,省选，SAM 求字典序第 大子串。

HINT：字典序第 大的子串对应于 SAM 中字典序第 大的路径，因此在计算每个状态的路径数后，我们可以很容易地从 SAM 的根开始找到第 大的路径。

T2,【模板】最小表示法,提高省选，SAM 求最小表示法。

HINT：容易发现字符串 包含字符串 的所有循环移位作为子串。所以问题简化为在 对应的后缀自动机上寻找最小的长度为 的路径。

Query：你还记得他的更简便的求法吗？

T3-1,LCS,省选&&T3-2,LONGCS,省选&&T3-3,LCS2,省选，SAM 求两个/多个字符串的最长公共子串。

HINT1：求两个的话，我们可以构造出一个字符串的 SAM，我们现在处理另一个字符串，对于每一个前缀，都在 SAM 中寻找这个前缀的最长后缀，求最大值即可。转移的时候，类似于 KMP 的跳 ，ACAM 的跳失配指针，我们跳后缀链接并更新长度即可。

HINT2：求多个的话，我们将所有的子串连接成一个较长的字符串 ，以特殊字符 分开每个字符串（一个字符对应一个字符串）：。然后对字符串 T 构造后缀自动机。答案就是最深的且它的子树中具有所有分节符的非叶子节点。

T4,[SDOI2016] 生成魔咒,省选，动态求本质不同子串的个数。

HINT：每次新出现的本质不同的子串个数就等于 。

还有很多啊，比如出现次数，第一次出现的位置，所有出现的位置等，但是大多可以用 ACAM 吃掉。

依据这个帖子，SA 胜过 SAM 的地方在于 SAM 不能（或者很难） 比较两个后缀的字典序（by 366338），而 SAM 中的 却可以用来干很多恶心人的事。不过，二者似乎可以在 的时间内互相转化，因此不太存在只能用其一解的题。

Tip：有的文章会说在牺牲一点点效率的情况下可以做到严格线性的空间复杂度，带 或常数的时间复杂度，但是实际上，map<int,int> 在 gcc 下初始状态下会占 ，unordered_map<int,int> 更是会占到 。前者相当于 个 int，后者相当于 个 int。因此，实际应用中（多为小写字母 大小字符集），可以酌情选择前者，一定不要选择后者。

后缀数组

部分进阶知识可以参见这篇集训队论文。

SA，全称 ，译为后缀数组。 在所有后缀中的字典序升序排名的第 个后缀的开始位置，表示的是 表示的是后缀 在所有后缀中的字典序升序排名。 表示 。

怎么求 呢？首先有一种暴力的 的做法。我们将所有的后缀拿过来排序。这不是 的吗？但事实上，比较两个字符串就是在比较它们第一处不一样的位置的大小。因此我们可以用 Hash+BinarySearch 优化到 。

但是这样做时间复杂度仍然有些高，能不能优化到 呢？可以，不过我们换一种方式。

假如说我们已经排出了这些后缀在考虑前 个字符时的大小，那么怎么拓展到 个字符呢？显然我们只需要对有序二元组 排序就行了。正确性显然。

但是这样不还是 的吗？不是。不难注意到 ，也就是说我们可以不基于比较进行排序。我们采用计数排序。

欸？二维的怎么计数排序？很简单啊，先把第二维升序排了再把第一维顺序排了。

那你的 数组怎么处理？最后处理吗？显然不是，计数排序的时候我们就需要 数组。但是一定要注意 只在两维都排完之后才会更新。毕竟两次排序本质上是一次二维排序。你中间就把排名改了能对就怪了。

这样就优化到 了。还能更优吗？可以。你可以使用 SA-IS 算法做到 ，他要更优于 DC3。为什么？因为提高了缓存命中率（喜）。

这不重要，来看 数组吧。首先很显然， 数组仍然可以用 Hash+BinarySearch 做到 ，但是能不能更优呢？

可以的。很难(?)注意到一个性质：。总之，有了这个性质，我们就可以暴力模拟这个性质获得 的简短的算法。为什么是 呢？因为最多 次减一，对应最多 次加一。

比模板题更模板的模板题代码如下：

计算几何

计几基础概念

首先我写代码习惯上会把点和向量视为同一种类型，毕竟向量的坐标表示很像点，因此向量加减和点加减等等一系列的操作本质相同。

 

小技巧

搜索序限制区间

搜索序，这里指的是 dfs 序。也就是用 dfs 序来限制区间，典型的应用有 dfs 序求 LCA，路径起止点限制转二维数点。前者已经讲过了，我简述一下后者及其重要性。

我们有时候会遇到一些统计题，这些题一般会是在树上的某种路径计数，或者树上的路径的某种“权值”的最大值。你常常能够转化出一些限制了端点(不)在某些子树内的要求。

通过 dfs 序，我们可以将任意一个子树对应到 dfs 序上的一个区间，从而将任意两个端点限制在一个矩形内。这个矩形的横纵坐标区间分别对应着两个端点的子树对应的区间。

转化完毕后再利用扫描线，kdtree，二维线段树等等神秘黑科技去维护。

区间加转差分

这种技巧非常常见而且十分灵活。常见于用来优化数据结构，比如树状数组处理区间加区间求和。这里另提一道好题：Power Tree。

看起来和这个技巧真的毫无关系，但是我们发现如果我们用 dfs 序把这颗树给拍扁了，那控制一个顶点就相当于可以对一个连续的区间进行区间加。这时候，我们区间加转差分，相当于每一个点可以将一个位置的贡献总和不变的挪动到另一个位置。

我们最后的目标是所有点的值是 ，也就是在前 个位置的差分数组总是为 ，因此我们可以使用最小生成树来将选择可用边，使得其总能转移到 这一限制条件转化为最小生成树！

于是我们将树上的问题先通过 dfs 序转化为了序列加，再将序列加通过差分转变为点值移动，最后抽象出最小生成树的图论模型解决，十分巧妙。

逐步可行

对于大部分的构造题，你会需要满足多个条件。

这时候一种可行的方式是“逐步可行”，理解为逐个满足所有条件，先满足一个，再通过调整向后依次满足。

比如这道题，要求满足一些位置的和为给定值的前提下每一个值在 之间。

一种可行的解法是先构造出来一组不考虑值域限制的解，然后观察到对于每一行列交替加减同一值仍然满足要求。

于是我们通过限制加减的结果的范围构造差分约束并进行求解。

上升下降幂预处理组合数

。因此对于此类组合数可以通过预处理 的上升幂和 的逆元快速求解。

。因此对于此类组合数可以通过预处理 的下降幂和 的逆元快速求解。

其中第一类常见模型是 。第二类则更加朴素。

哈希判等价类

很简单的算法，主要是想不到。想不到就放这里供着。

举个例题：在一个 的区间上有若干个区间 ，初始时 。每一次你可以选择 或者 ，求最终的 的大小的最大值。

我们注意到，对于一个 ，他一定导致这一部分的状态统一发生改变，无论是全部可选还是全部不可选。

因此，对于每一次操作，我们将 中的所有位置异或上一个随机值。最后在期望意义下，状态一样的位置的哈希值也是一样的。我们从中选出出现次数最多的那个值的出现次数作为答案即可。

尺取法

很简单的算法，主要是想不到。想不到就放这里供着。这是例题，也是点分治的讲解例题。如果不想思考建议先行阅读解法的前半部分。

所谓尺取法，就是根据限制的单调性，维护一个可行区间的若干信息，从而方便转移。比如在这道题中，注意到 恒正，所以我们考虑对于 和 的情况分开验证。

我们以 的情况为例。限制为 。显然，这个限制有解当且仅当存在一个 对于特定的 满足 比 小。

于是我们考虑将 按照 从小到大排序。那么不难注意到，从前往后枚举 的话，满足要求的 一定是一个后缀。因此我们在枚举的过程中动态加入新的满足要求的 并维护 的最小值即可做。

一言以蔽之，利用决策单调性动态维护可行决策区间的状态。